代码随想录算法训练营第55天 | 42. 接雨水 、84.柱状图中最大的矩形

42. 接雨水

接雨水这道题目是 面试中特别高频的一道题，也是单调栈 应用的题目，大家好好做做。
建议是掌握 双指针 和单调栈，因为在面试中 写出单调栈可能 有点难度，但双指针思路更直接一些。
在时间紧张的情况有，能写出双指针法也是不错的，然后可以和面试官在慢慢讨论如何优化。
https://programmercarl.com/0042.接雨水.html

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    if (height.length <= 2) {
        return 0;
    }
    const len = height.length;
    const stack = [0];
    let res = 0;
    for (let i=1; i<len;i++) {
        while(stack.length && height[stack[stack.length - 1]] < height[i]) {
            let mid = stack.pop();
            if (stack.length >= 1) {
                let left = stack[stack.length - 1];
                let min = Math.min(height[i], height[left]);
                res += (i- left -1) * (min - height[mid]);
            }
        }
        stack.push(i);
    }
    return res;
};

84.柱状图中最大的矩形
有了之前单调栈的铺垫，这道题目就不难了。
https://programmercarl.com/0084.柱状图中最大的矩形.html

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
    let maxArea = 0;
	const stack = [0];
	heights.push(0);
	const n = heights.length;

	for (let i = 1; i < n; i++) {
        let top = stack.at(-1)
        if (heights[top] < heights[i]) {
            stack.push(i);
        } else if (heights[top] === heights[i]) {
            stack.push(i);
        } else {
            while(stack.length && heights[top] > heights[i]) {
                const h = heights[stack.pop()];
                const left = stack.at(-1)?? -1;
                const w = i - left -1;
                maxArea = Math.max(maxArea, w*h);
                top = stack.at(-1);
            }
            stack.push(i)
        }
    }
	return maxArea;
};