Create 962.Maximum-Width-Ramp.cpp

wisdompeak · web-flow · commit dcafbfbdaa72 · 2018-12-25T00:26:56.000-08:00
diff --git a/Stack/962.Maximum-Width-Ramp/962.Maximum-Width-Ramp.cpp b/Stack/962.Maximum-Width-Ramp/962.Maximum-Width-Ramp.cpp
@@ -0,0 +1,33 @@
+class Solution {
+public:
+    int maxWidthRamp(vector<int>& nums) 
+    {
+        vector<int>q;
+        vector<int>idx;
+        int result = 0;
+        
+        for (int i=0; i<nums.size();i++)
+        {
+            if (q.size()==0)
+            {
+                q.push_back(nums[i]);
+                idx.push_back(i);
+                continue;
+            }
+            
+            if (q.size()>0 && nums[i]<q.back())
+            {
+                q.push_back(nums[i]);
+                idx.push_back(i);
+            }
+            else
+            {
+                auto it = upper_bound(q.rbegin(),q.rend(),nums[i]);
+                int k = it-q.rbegin();
+                k = q.size()-1-k + 1;
+                result = max(result, i-idx[k]);                
+            }            
+        }        
+        return result;
+    }
+};
