面试必刷算法TOP101之单调栈问题 TOP 24

下一个元素更大Ⅱ

题目来源：leetcode

1、问题描述

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
示例：

2、思路解析

思路一：暴力循环破解
首先根据题意说明数组是一个循环数组，说明最后一天也有结果，所以数组最少遍历两边。同样还是双for循环，外层循环遍历数组元素，内层循环循环右边第一个比当前值大的数组，保存并跳出循环。最后将ans结果数组返回回去。但是因为每次for循环都要遍历至少完两边所以时间复杂度为(O(2N^2));
思路二：循环数组的单调栈
思路就是将一个一个元素入栈，定义一个栈s，这不像其他栈一样，他是一个单调栈，所谓单调栈就是从栈顶到栈地数据是递增的但不是像其他栈那样直接入栈，而是又顺序入栈，栈中元素是递减的或者递增的，因为题意要知道当前之后，多少个数据之后气温会比当前数据高，因为下标+1就是对应的数据，所以将对应的数组下标存入到单调栈中，其所对应的值不是递增就是递减的。for循环从1开始遍历元素，当遇到栈顶元素比当前元素小因为要保证栈中元素是有序的，所以将栈中元素小于当前元素都出栈，同时出栈元素也是数组下标，将当先下标减去栈顶元素值存入到ans[s.top]中。与之前不同的是for循环退出条件就是遍历完数组两边。

3、代码实现

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {

        vector<int> v(nums.size(),-1);
     
       for(int i=0;i<2*nums.size();i++){
           int num1=i%nums.size();
            for(int j=i+1;j<2*nums.size();j++){
                  int num2=j%nums.size();
                  if(nums[num2]>nums[num1]){
                      v[num1]=nums[num2];
                      break;
                  }
                
            }
        }
        return v;
    }
};

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {

        vector<int> v(nums.size(),-1);
        stack<int> s;
        s.push(0);//0号元素入栈
       for(int i=1;i<2*nums.size();i++){
            int num=i%nums.size();
            //如果下边找到比当前值大的数据就更新数据
            while(!s.empty()&&nums[num]>nums[s.top()]){
                v[s.top()]=nums[num];
                s.pop();
            }
            //栈为NULL或者栈顶元素比新来元素大就将新来元素入栈
            s.push(num);
        }
        return v;
    }
};

接雨水

题目来源：leetcode

1、问题描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例：

2、思路解析

思路：单调栈
同样的栈中保存的是元素的下标，因为要保存雨水所以必须是后边的高度必定比前边的高度大，所以栈中元素时从栈底到栈顶是单调递减的。还是外层for循环遍历元素，内层while循环遍历栈直到栈为空或者栈顶元素比当前元素大。
为什么和之前一样单调栈可以解决解决这个问题？
先看一个例子：

取栈顶元素并将栈顶元素d出，d出为1所以这就是一个凹槽，能够接一个单位的雨水，d出的位置就是凹槽的中间位置，极为mid，栈顶height[s,top()]元素为凹槽左边的位置的高度，当前元素也就是凹槽右边的位置高度，那么接到的雨水的高度就是min(凹槽左边位置高度-凹槽右边高度)-凹槽中间高度，雨水宽度凹槽右边下标-凹槽左边下标-1也就是h=min(heginht[i],hegight[s.top()])-heigh[mid],w=i-s.top()-1.当前凹槽雨水的体积就是：h * w。
当遇到相同高度的柱子怎么办？取最右边的主子高度。
遇到相同的元素，更新栈内下标，就是将栈里元素（旧下标）d出，将新元素（新下标）加入栈中。
例如 5 5 1 3 这种情况。如果添加第二个5的时候就应该将第一个5的下标d出，把第二个5添加到栈中。因为我们要求宽度的时候 如果遇到相同高度的柱子，需要使用最右边的柱子来计算宽度。

还有当栈中元素只剩一个会直接跳出循环，为什么？
因为栈中只剩一个元素，这就只有凹槽的mid没有了凹槽的左边的高度了，这样接不到雨水，所以会直接跳出循环。

代码实现

class Solution {
public:
    int trap(vector<int>& height) {
        int ans=0;
        stack<int> s;
        for(int i=0;i<height.size();i++){
            while(!s.empty()&&height[i]>height[s.top()]){
                int num=s.top();
                s.pop();
                if(!s.empty()){
                //计算接雨水的高度
                int h=min(height[i],height[s.top()])-height[num];
                //计算接雨水的宽度
                int w=i-s.top()-1;
                //保存结果
                ans+=h*w;
                }

            } 
             s.push(i);
        }
        return ans;

    }
};

柱状图中最大的矩形

题目来源：leetcode

1、问题描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例：

2、思路解析

思路一：循环暴力破解+双指针
已知矩形面积=长*宽，我们可以固定一个寻找长或者宽的最大值，假如固定宽，款就为当前值的数值，然后双指针从当前向前或者先后扩展，寻找比当前值大或者等于的数据直到寻找到比当前值小的数据，就直接跳出内循环。左边界值为begin+1，右边界值为end-1.面积为heighti 每次循环都将面积最大直报存下来。最后返回ans。
看一个例子：

3、代码实现

class Solution {
public:
    //控制高度为当前值
    //扩散寻找宽度
    int largestRectangleArea(vector& heights) {
        int maxarea = 0;
        for (int i = 0;i < heights.size();i++) {
            //从当前位置向两边扩散
            int begin = i - 1;
            while (begin >= 0 && heights[begin] >= heights[i]) {
                //判断扩散位置小于当前位置就停止并跳出循环
                //左边界就为begin+1

                begin--;
            }
            int end = i + 1;
            while (end < heights.size() && heights[end] >= heights[i]) {
                //判断扩散位置小于当前位置就停止并跳出循环
                //右边界就为end-1
                end++;
            }
            //保存最大面积
            maxarea = max(maxarea, heights[i] * ((end-1) - (begin+1) + 1));
        }
        return maxarea;

    }
};