Day59| 503 下一个更大元素II 42 接雨水

目录

503 下一个更大元素II 

42 接雨水  

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        //因为没有下一个最大值的赋成-1，所以初始化成-1
        stack<int> st;
        //存放下一个更大的元素
        vector<int> result(nums.size(), -1);

        st.push(0);

        for(int i = 1; i < nums.size(); i++){
            //1 栈顶元素比较大,就把当前元素插进去
            if(nums[st.top()] > nums[i]){
                st.push(i);
            }//2 栈顶元素和当前元素相等,也插进去
            else if(nums[st.top()] == nums[i]){
                st.push(i);
            }//3 栈顶元素比当前元素小,说明找到值了
            else{
                while(!st.empty() && nums[st.top()] < nums[i]){
                    result[st.top()] = nums[i];
                    st.pop();
                }
                st.push(i);
            }
        }
        
        if(!st.empty()){
            for(int i = 0; i < nums.size(); i++){
                while(!st.empty() && nums[i] > nums[st.top()]){
                    result[st.top()] = nums[i];
                    st.pop();
                }
            }
        }
        return result;
    }
};

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        //保持遍历过的数组元素
        vector<int> result(height.size(), 0);
        int sum = 0;

        st.push(0);

        for(int i = 1; i < height.size(); i++){
            //1 栈的元素比较大
            if(height[st.top()] > height[i]){
                st.push(i);
            }//2 栈的元素和当前元素一样大，就有两种选择，一个是把元素加进来另一个是把之前的元素pop出去然后再加进来，实际上结果一样
            else if(height[st.top()] == height[i]){
                st.push(i);
            }//3 栈顶元素比较当前元素小
            else{
                while(!st.empty() && height[st.top()] < height[i]){
                    //记录此时的栈顶元素，就相当于是中间的那个方块高度
                    int mid = st.top();
                    st.pop();//pop之后此时的栈顶就是左边界，而当前元素是右边界
                    //找左右边界小的那个，因为短板，然后减去中间的那个板就是高度了
                    if(!st.empty()){
                        int h = min(height[st.top()], height[i]) - height[mid];
                        int w = i - st.top() - 1;
                        sum += h * w;
                    }
                }
                st.push(i);
            }
        }
        return sum;
    }
};