单调栈复习01_230617

主要关注栈内元素放置的是什么

栈头-栈尾递增还是递减，寻找右侧最大元素，则栈内元素递增；

例如Leetcode的每日温度，实则寻找右侧首个大于自身的元素位置，则栈内元素为下标、栈内元素逐渐增大，如果遍历到的元素小于栈顶元素则入栈，否则出栈

主要逻辑如下：

    vector<int> dailyTemperatures(vector<int>& temperatures) {
       //寻找右侧最大元素 栈顶-栈底 递增
       int size = temperatures.size();
       stack<int>st;
       vector<int>ans(size,0);
       st.push(0);
        for (int i = 1; i < size; ++i) {
            while(!st.empty() && temperatures[i] > temperatures[st.top()]){
               ans[st.top()] = i - st.top();
                st.pop();
//                st.push(i);
            }
            st.push(i);
        }
        return ans;
    }

其次，接雨水与最大矩形面积则是寻找左右两侧最大值，然后考虑木桶效应，找完最大值之后进行比较选择较小者。
主要逻辑如下：
接雨水：

   int trap(vector<int>& height) {
        stack<int>st;
        st.push(0);
        int sum = 0;
        for (int i = 1; i < height.size(); ++i) {
            //栈中元素为vector的下标
            //栈中元素从栈头到栈尾关系为从小到大

            while (!st.empty() && height[st.top()] < height[i]){
                int mid =  st.top();
                st.pop();
                if (!st.empty()){
                    int w = i - st.top() - 1;
                    int h = min(height[st.top()],height[i]) - height[mid];
                    sum += h * w;
                }
            }
            st.push(i);
        }
        return sum;
    }

最大柱形图面积：

int largestRectangleArea(vector<int>& height) {       
   height.insert(height.begin(),0);
        stack<int> st;
        int ans = 0;
        st.push(0);
        for (int i = 1; i < height.size(); ++i) {
            if (height[i] > height[st.top()]){
                st.push(i);
            } else if (height[i] == height[st.top()]){
                st.pop();
                st.push(i);
            } else{
                while (!st.empty() && height[i] < height[st.top()]){
                    int mid =st.top();
                    st.pop();
                    if (!st.empty()){
                        int h = height[mid];//min(height[i], height[st.top()]) -
                        int w = i - st.top() - 1;
                        ans = max(ans, h * w);
                    }
                }
                st.push(i);
            }
        }
        return ans;
    }

双指针法也可以解决柱形图和接雨水问题：

柱形图面积：

//双指针法
    int largestRectangleArea(vector<int>& height) {
        /*int size = height.size();
        vector<int>minLeftIndex(size,0);
        vector<int>minRightIndex(size,0);
        minLeftIndex[0] = -1;
        for (int i = 1; i < size; ++i) {
            int t = i - 1;
            //寻找左侧第一个小于本柱子的下标
            while(t >= 0 && height[t] >= height[i]) t =minLeftIndex[t];
            minLeftIndex[i] = t;
        }
        for (const auto &item: minLeftIndex)
            cout << "item: " << item ;
        cout << endl;
        minRightIndex[size - 1] = size;
        for (int i = size - 2; i >=0; i--) {
            int t = i + 1;
            //寻找右侧第一个小于本柱子的下标
            while(t < size && height[t] >= height[i]) t = minRightIndex[t];//此处为何取到=
            minRightIndex[i] = t;
        }

        for (const auto &item: minRightIndex)
            cout << "item: " << item ;
        int result= 0;
        for (int i = 0; i < size; ++i) {
            int sum = height[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
            result = max(sum,result);
        }
        return result;
    }

接雨水：

//双指针优化
       int size = height.size();
        vector<int> maxLeftHeight(size);
        vector<int> maxRightHeight(size);
        maxLeftHeight[0] = height[0];
        for (int i = 1; i < size; ++i) {
            maxLeftHeight[i] = max(maxLeftHeight[i - 1],height[i]);
        }
        maxRightHeight[size - 1] = height[size - 1];
        for (int i = size - 2; i >= 0 ; i--) {
            maxRightHeight[i] = max(maxRightHeight[i + 1],height[i]);
        }

        int sum = 0;
        for (int i = 0; i < size; ++i) {
            int count = min(maxLeftHeight[i],maxRightHeight[i]) - height[i];
            if (count > 0) {
                cout << count << endl;
                sum += count;
            }
        }
        return sum;