503.下一个更大元素II

一遍过，走两圈%一下遍历，控制入栈只在第一圈即可。

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> res(nums.size(), -1);
        stack<int> st;

        for (int i = 0; i < nums.size() * 2; i++) {
            while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
                res[st.top()] = nums[i % nums.size()];
                st.pop();
            }
            if (i < nums.size()) {
                st.push(i);
            }
        }
        return res;

    }
};

42. 接雨水

注意，如果当前遍历的元素（柱子）高度等于栈顶元素的高度，要跟更新栈顶元素，因为遇到相相同高度的柱子，需要使用最右边的柱子来计算宽度。

• 当当前元素大于栈顶时，栈顶就是凹形的底部，栈顶下一个元素就是左边界，最好画图模拟一下比较细节。

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

};

暴力双指针，从列来看，雨水的高度= 两侧最矮的高度-当前位置高度, 用双指针找两边最高的。

//每次都双指针向两边寻找，会超时
class Solution {
public:
    int trap(vector<int>& T) {
        int sum = 0;
        for (int i = 0; i < T.size(); i++) {
            if (i == 0 || i == T.size() - 1) continue;
            int rHeight = T[i];
            int lHeight = T[i];
            for (int r = i + 1; r < T.size(); r++) {
                if (T[r] > rHeight) rHeight = T[r];
            }
            for (int l = i - 1; l >= 0; l--) {
                if (T[l] > lHeight) lHeight = T[l];
            }
            int h = min(lHeight, rHeight) - T[i];
            sum += h;
        }
        return sum;
    }

};
//先记录两边最高的，可以重复利用，用空间换时间，避免超时
class Solution {
public:
    int trap(vector<int>& T) {
        int sum = 0;
        vector<int> maxL(T.size());
        vector<int> maxR(T.size());
        maxL[0] = T[0];
        maxR[T.size() - 1] = T[T.size() - 1];
        for (int i = 1; i < T.size(); i++) {
            maxL[i] = max(T[i], maxL[i - 1]);
        }
        for (int i = T.size() - 2; i >= 0 ; i--) {
            maxR[i] = max(T[i], maxR[i + 1]);
        }
        for (int i = 0; i < T.size(); i++) {
            if (i == 0 || i == T.size() - 1) continue;
            int h = min(maxL[i], maxR[i]) - T[i];
            sum += h;
        }
        return sum;
    }

};