【代码随想录】day59

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

一、503下一个更大元素II

跟上道题本质上一样，多转一圈就行。

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, -1);
        stack<int> st;
        st.push(0);
        for (int i = 1; i < 2 * n; i ++) {
            int index = i % n;
            while (!st.empty() && nums[index] > nums[st.top()]) {
                res[st.top()] = nums[index];
                st.pop();
            }
            st.push(index);
        }
        return res;
    }
};

二、42接雨水

以前背过，现在忘了，就连暴力法都是看了思路写的…
暴力法按列（勉强能过）：

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int res = 0;
        int maxLeft = 0;
        for (int i = 1; i < n - 1; i ++) {
            //计算第i根柱子接多少
            int maxRight = 0;
            maxLeft = max(maxLeft, height[i-1]);
            for (int right = n - 1; right > i; right --) {
                maxRight = max(maxRight, height[right]);
            }
            maxLeft = min(maxLeft, maxRight);
            res += max(0, maxLeft - height[i]);
        }
        return res;
    }
};

优化（空间换时间）：

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int res = 0;
        vector<int> maxLeft(n, height[0]);
        vector<int> maxRight(n, height[n-1]);
        for (int i = 1; i < n; i ++) {
            maxLeft[i] = max(maxLeft[i-1], height[i]);
        }
        for (int j = n - 2; j >= 0; j --) {
            maxRight[j] = max(maxRight[j+1], height[j]);
        }
        for (int i = 1; i < n - 1; i ++) {
            //计算第i根柱子接多少
            int num = min(maxLeft[i-1], maxRight[i+1]);
            res += max(0, num - height[i]);
        }
        return res;
    }
};

单调栈：

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int res = 0;
        stack<int> st;
        st.push(0);
        for (int i = 1; i < n; i ++) {
            while (!st.empty() && height[i] > height[st.top()]) {
                int mid = height[st.top()];
                st.pop();
                if (!st.empty()) {
                    int h = min(height[i], height[st.top()]);
                    int w = i - st.top() - 1;
                    res += (h - mid) * w;
                }
            }
            st.push(i);
        }
        return res;
    }
};