Sliding window, double pointer, monotone queue, monotone stack

The sliding window 、 Double pointer 、 A monotonous queue 、 Monotonic stack

LeetCode. 32 Longest valid bracket

• Bracket sequence is legal <=> All prefixes and >= 0 And cnt == 0
• start: The beginning of this paragraph of the current enumeration
• cnt: The prefix and
• ( = 1
• ) = -1
• What happens during enumeration ：
  1. cnt < 0 : start = i + 1, cnt = 0;
  2. cnt > 0 : go on
  3. cnt == 0 : eligible ,res = max(res, i - start + 1)
• a key ： Yes s Traverse both positive and negative once , Take the maximum of them

class Solution {
    
public:
    int work(string &s) {
    
        int res = 0;
        for(int i = 0, start = 0, cnt = 0; i < s.size(); ++i) {
    
            if(s[i] == '(') ++cnt;
            else --cnt;

            if(cnt < 0) start = i+1, cnt = 0;
            else if(cnt == 0) res = max(res, i - start + 1);
        }
        return res;
    }
    int longestValidParentheses(string s) {
    
        int ans1 = work(s);
        for(auto &c:s)
            c ^= 1;
        reverse(s.begin(), s.end());
        return max(ans1, work(s));
    }
};

LeetCode. 84 The largest rectangle in the histogram

• Enumerate the upper boundaries of all columns , As the upper boundary of the whole rectangle , Then find the left and right boundaries

• Find left and right boundaries ： Find the left side closest to it 、 The smaller cylindrical position left

  ​ Find the right side closest to it 、 The smaller cylindrical position right

class Solution {
    
public:
    int largestRectangleArea(vector<int>& heights) {
    
        int n = heights.size();
        vector<int> left(n), right(n);

        stack<int> stk;
        for(int i = 0; i < n; ++i) {
    
            while(stk.size() && heights[stk.top()] >= heights[i]) stk.pop();
            if(stk.empty()) left[i] = -1;
            else left[i] = stk.top();
            stk.push(i);
        }
        while(stk.size()) stk.pop();
        for(int i = n - 1; i >= 0; --i) {
    
            while(stk.size() && heights[stk.top()] >= heights[i]) stk.pop();
            if(stk.empty()) right[i] = n;
            else right[i] = stk.top();
            stk.push(i);
        }

        int res = 0;
        for(int i = 0; i < n; ++i) {
    
            res = max(res, heights[i] * (right[i] - left[i] - 1));
        }
        return res;
    }
    
};

LeetCode. 42 Rainwater collection

class Solution {
    
public:
    int trap(vector<int>& height) {
    
        int res = 0;
        stack<int> stk;

        for(int i = 0; i < height.size(); ++i) {
    
            int last = 0;
            while(stk.size() && height[stk.top()] <= height[i]) {
    
                int t = stk.top();
                stk.pop();
                res += (height[t] - last) * (i - t - 1);
                last = height[t];
            }
            if(stk.size()) {
    
                res += (height[i] - last) * (i - stk.top() - 1);
            }
            stk.push(i);
        }
        return res;
    }
};

LeetCode. 239 Maximum sliding window

class Solution {
    
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    
        vector<int> res;
        deque<int> q;
        for(int i = 0; i < nums.size(); ++i) {
    
            if(q.size() && i - k >= q.front()) q.pop_front();
            while(q.size() && nums[q.back()] <= nums[i]) q.pop_back();
            q.push_back(i);
            if(i >= k - 1) res.push_back(nums[q.front()]);
        }
        return res;
    }
};

LeetCode. 918 The maximum sum of the ring subarray

class Solution {
    
public:
    int maxSubarraySumCircular(vector<int>& nums) {
    
        int n = nums.size();
        for(int i = 0; i < n; ++i) nums.push_back(nums[i]);
        vector<int> s(2 * n + 1, 0);
        for(int i = 1; i < 2*n+1; ++i) s[i] = s[i-1] + nums[i-1];

        int res = INT_MIN;
        deque<int> q;
        q.push_back(0);
        for(int i = 1; i < 2*n+1; ++i) {
    
            if(q.size() && i - q.front() > n) q.pop_front();
            if(q.size()) res = max(res, s[i] - s[q.front()]);
            while(q.size() && s[q.back()] >= s[i]) q.pop_back();
            q.push_back(i);
        }
        return res;
    }
};