代码随想录算法训练营day48：单调栈

739. 每日温度

503.下一个更大元素II

分析：

42. 接雨水

本质：

暴力解法分析：

双指针优化

单调栈

84.柱状图中最大的矩形

分析：

双指针：

单调栈

739. 每日温度

力扣题目链接(opens new window)

请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

分析：

此时有同学可能就疑惑了，那result[6] , result[7]怎么没更新啊，元素也一直在栈里。

其实定义result数组的时候，就应该直接初始化为0，如果result没有更新，说明这个元素右面没有更大的了，也就是为0。

注意~~：储存下标时，写代码很容易写错！要注意

int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize) {
    int s[temperaturesSize];//记录的是温度的下标
    int top=-1;

    for(int i=0;i<temperaturesSize;i++){
        if(top==-1 || temperatures[s[top]]>=temperatures[i]) s[++top]=i;
        else {
            while(top!=-1 && temperatures[s[top]]<temperatures[i]){
                int x=s[top];
                
                temperatures[x]=i-x;
                top--;
            }
            s[++top]=i;
        }
    }

    while(top!=-1){
        temperatures[s[top]]=0;
        top--;
    }
    *returnSize=temperaturesSize;
    return temperatures;
}

503.下一个更大元素II

力扣题目链接(opens new window)

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

示例 1:

输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数；第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

提示:

1 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9

分析：

思路：

相当于循环两遍nums数组

取最大值的情况照旧

但对于第二轮循环时，有些元素已经完成计算，此时不需要计算覆盖情况，continue掉

runtime error: load of null pointer of type ‘int‘

该题需要return一个数组，而在不申请空间（不malloc）的情况下函数内建立的数组是局部变量，无法带回主函数。

所以在开辟需要返回的数组空间时，在leetcode里需要用malloc

复杂度：o（n），o（n）

int* nextGreaterElements(int* nums, int numsSize, int* returnSize) {
    int index[2*numsSize];//index存放的数值，第二轮会比第一轮大numssize
    int top=-1;
    int *ans;
    ans=(int*)malloc(sizeof(int)*2*numsSize);
    for (int i=0;i<numsSize;i++){
        ans[i]=-1;//初始化为-1,因为没找到最大的数，就会赋值为-1；
    }
    //i在0~2n，ans、nums要求0~n,index要求0~2n

    for(int i=0;i<numsSize*2;i++){//如果存在下一个更大的数，循环两轮一定能找到
        //进栈的情况
        if(top == -1 || nums[index[top]%numsSize] >= nums[i%numsSize]) {
            index[++top]=i;
        }

        //出栈;是否要计算
        else {
            while(top!=-1 && nums[index[top]%numsSize] < nums[i%numsSize]){
                int x = index[top];
                if(ans[x%numsSize]!=-1) {
                    top--;
                    continue;
                }
                ans[x%numsSize]=nums[i%numsSize]; 
                top--;
            }
            index[++top]=i;
        }
    }
    *returnSize=numsSize;
    return ans;
}

42. 接雨水

力扣题目链接(opens new window)

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

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

本质：

这种类型的题目可以从两个方向讨论：

按列看：

左边最高的柱子，右边最高的柱子，会围成一个凹槽，可以放水

每一列的雨量=min（两边最高）-本列高度

按行看：

按照一个个凹槽来求

暴力解法分析：

如果按照列来计算的话，宽度一定是1了，我们再把每一列的雨水的高度求出来就可以了。

可以看出每一列雨水的高度，取决于，该列左侧最高的柱子和右侧最高的柱子中最矮的那个柱子的高度。

这句话可以有点绕，来举一个理解，例如求列4的雨水高度，如图：

42.接雨水3

列4 左侧最高的柱子是列3，高度为2（以下用lHeight表示）。

列4 右侧最高的柱子是列7，高度为3（以下用rHeight表示）。

列4 柱子的高度为1（以下用height表示）

那么列4的雨水高度为列3和列7的高度最小值减列4高度，即： min(lHeight, rHeight) - height。

列4的雨水高度求出来了，宽度为1，相乘就是列4的雨水体积了。

此时求出了列4的雨水体积。

一样的方法，只要从头遍历一遍所有的列，然后求出每一列雨水的体积，相加之后就是总雨水的体积了。

首先从头遍历所有的列，并且要注意第一个柱子和最后一个柱子不接雨水，代码如下：

for (int i = 0; i < height.size(); i++) {
    // 第一个柱子和最后一个柱子不接雨水
    if (i == 0 || i == height.size() - 1) continue;
}

在for循环中求左右两边最高柱子，代码如下：

int rHeight = height[i]; // 记录右边柱子的最高高度
int lHeight = height[i]; // 记录左边柱子的最高高度
for (int r = i + 1; r < height.size(); r++) {
    if (height[r] > rHeight) rHeight = height[r];
}
for (int l = i - 1; l >= 0; l--) {
    if (height[l] > lHeight) lHeight = height[l];
}

最后，计算该列的雨水高度，代码如下：

int h = min(lHeight, rHeight) - height[i];
if (h > 0) sum += h; // 注意只有h大于零的时候，在统计到总和中

时间复杂度为O(n^2)，空间复杂度为O(1)——超时

双指针优化

区别于单调栈问题！！单调栈找的是附近的最大值、最小值；如果按照列求，实际上找的是左边\右边的最大值，而不是最近的大值

在暴力解法中，我们可以看到只要记录左边柱子的最高高度和右边柱子的最高高度，就可以计算当前位置的雨水面积，这就是通过列来计算。

当前列雨水面积：min(左边柱子的最高高度，记录右边柱子的最高高度) - 当前柱子高度。

为了得到两边的最高高度，使用了双指针来遍历，每到一个柱子都向两边遍历一遍，这其实是有重复计算的。我们把每一个位置的左边最高高度记录在一个数组上（maxLeft），右边最高高度记录在一个数组上（maxRight），这样就避免了重复计算。

当前位置，左边的最高高度是前一个位置的左边最高高度和本高度的最大值。

即从左向右遍历：maxLeft[i] = max(height[i], maxLeft[i - 1]);

从右向左遍历：maxRight[i] = max(height[i], maxRight[i + 1]);

代码如下：

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.size() <= 2) return 0;
        vector<int> maxLeft(height.size(), 0);
        vector<int> maxRight(height.size(), 0);
        int size = maxRight.size();

        // 记录每个柱子左边柱子最大高度
        maxLeft[0] = height[0];
        for (int i = 1; i < size; i++) {
            maxLeft[i] = max(height[i], maxLeft[i - 1]);
        }
        // 记录每个柱子右边柱子最大高度
        maxRight[size - 1] = height[size - 1];
        for (int i = size - 2; i >= 0; i--) {
            maxRight[i] = max(height[i], maxRight[i + 1]);
        }
        // 求和
        int sum = 0;
        for (int i = 0; i < size; i++) {
            int count = min(maxLeft[i], maxRight[i]) - height[i];
            if (count > 0) sum += count;
        }
        return sum;
    }
};

单调栈

应用范围：通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。

而接雨水这道题目，我们正需要寻找一个元素，右边最大元素以及左边最大元素，来计算雨水面积。

最关键：直接用单调栈，通过栈顶、栈顶的下一个元素、即将入栈元素，三个为一组，计算盛的雨水

int trap(int* height, int heightSize) {
    int sum=0;

    int s[heightSize];//存放location
    int top=-1;
    for(int i=0;i<heightSize;i++){
        if(top==-1 || height[s[top]] > height[i]) s[++top]=i;
        else if(height[s[top]] == height[i]) s[top]=i;
        else {
            while(top!=-1 && height[s[top]] < height[i]){
                int mid= s[top--];
                if(top>=0){
                    int left=s[top];
                    sum += fmin(height[i]-height[mid],height[left]-height[mid])*(i-left-1);
                    printf("left=%d mid=%d right=%d sum=%d \n",left,mid,i,sum);
                }
            }
            s[++top]=i;
        }
    }
    return sum;
}

84.柱状图中最大的矩形

力扣题目链接(opens new window)

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

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

分析：

对于每个柱子本体，考虑最终矩形高度为自身高度的情况

找左边第一个更矮的柱子，找右边第一个更矮的柱子——最宽能宽到哪里

同理也可以用暴力算法、双指针、单调栈

双指针：

记录每个柱子左边\右边第一个小于该柱子的下标

和接雨水有区别

因为找左边\右边第一个小于该柱子的下标，而不是左边最大的

如果要一个个遍历，那么就是暴力法了

既然开辟了数组，那就利用数组来简化

分为两种情况讨论：

1、找左边第一个比本体矮的：

最外层从左到右循环，j从i-1开始往前，当hj比hi大时——跳到hj左边第一个比j矮的即leftmin[j]

hj比hi小——找到了，就是j

2、右边：

从右到左循环！左侧的需要建立在右侧已经找到的基础上

int largestRectangleArea(int* heights, int heightsSize) {
    int leftmin[heightsSize];
    int rightmin[heightsSize];
    for (int i=0;i<heightsSize;i++){
        leftmin[i]=-1;
        rightmin[i]=heightsSize;
    }

    for(int i=1;i<heightsSize;i++){
        int j=i-1;
        while(j>=0){
            if(heights[j] < heights[i]){
                leftmin[i]=j;
                break;
            }
            j=leftmin[j];
        }
    }

    for(int i=heightsSize-2;i>=0;i--){
        int k=i+1;
        while(k<heightsSize){
            if(heights[k] <heights[i] ){
                rightmin[i]=k;
                break;
            }
            k=rightmin[k];
        }
    }

    int ansmax=0;
    for(int i=0;i<heightsSize;i++){
        int h=heights[i];
        int l=rightmin[i]-leftmin[i]-1;
        ansmax=fmax(ansmax, l*h);
        printf("%d %d %d \n",leftmin[i],rightmin[i],ansmax);

    }
    return ansmax;

    
}