leetcode84：柱状图中最大的矩形

题目链接

leetcode

题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

C++ 代码

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void printArray(vector<int>& arr)
{
	for (auto x : arr) {
		cout << x << " ";
	}
	cout << endl;
}

/*
    TLE, 超出时间限制

    在柱状图中找出最大的矩形，考虑枚举矩形的宽和高，
    其中「宽」表示矩形贴着柱状图底边的宽度，「高」表示矩形在柱状图上的高度。
    
    枚举「宽」，两重循环枚举矩形的左右边界以固定宽度 w，
    此时矩形的高度 h，就是所有包含在内的柱子的「最小高度」，对应的面积为 w*h。
    
    枚举「高」，一重循环枚举某一根柱子，将其固定为矩形的高度 h。
    从这跟柱子开始向两侧延伸，直到遇到高度小于 h 的柱子，就确定了矩形的左右边界。
    如果左右边界之间的宽度为 w，那么对应的面积为 w*h。

    时间复杂度：O(n^2) 
        考虑到枚举「宽」的方法使用了两重循环，不容易优化。
        因此，考虑优化只使用了一重循环的枚举「高」的方法。
    空间复杂度：O(1)
*/
// 枚举宽
class Solution_0 {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        int res = 0;
        // 枚举左边界
        for (int left = 0; left < n; left ++) {
            int minHeight = INT_MAX;
            // 枚举右边界
            for (int right = left; right < n; right ++) {
                // 确定高度，计算面积
                minHeight = min(minHeight, heights[right]);
                res = max(res, (right - left + 1) * minHeight);
            }
        }

        return res;
    }
};
// 枚举高
class Solution_1 {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        int res = 0;
        // 枚举高
        for (int i = 0; i < n; i ++) {
            int height = heights[i];
            int left = i, right = i;
            // 确定左右边界
            while (left - 1 >= 0 && heights[left - 1] >= height) {
                left --;
            }
            while (right + 1 < n && heights[right + 1] >= height) {
                right ++;
            }
            // 计算面积
            res = max(res, (right - left + 1) * height);
        }

        return res;
    }
};

/*
    单调栈：
        枚举「高」，对于某一根柱子的高度为 h，向左右两边扩展，使得柱子的高度均不小于 h。
        找到左右两侧最近的高度小于 h 的柱子，这两根柱子之间的所有柱子高度均不小于 h。

    时间复杂度：O(n)
        遍历数组时，对栈的操作的次数为 O(n)。
    空间复杂度：O(n)
        栈的大小为 O(n)。
*/
class Solution_2 {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n), right(n);

        stack<int> stk;
        for (int i = 0; i < n; i ++) {
            while (!stk.empty() && heights[stk.top()] >= heights[i]) {
                stk.pop();
            }
            if (stk.empty()) left[i] = -1;
            else left[i] = stk.top();
            stk.push(i);
        }

        stk = stack<int>();
        for (int i = n - 1; i >= 0; i --) {
            while (!stk.empty() && heights[stk.top()] >= heights[i]) {
                stk.pop();
            }
            if (stk.empty()) right[i] = n;
            else right[i] = stk.top();
            stk.push(i);
        }

        int res = 0;
        for (int i = 0; i < n; i ++) {
            res = max(res, (right[i] - left[i] - 1) * heights[i]);
        }
        return res;
    }
};

/*
    单调栈

    1.找到每个柱子左右两边最近且低于自身高度的，宽度乘高度作为备选答案。
    2.维护一个单调递增的栈，
        如果当前柱子 i 的高度比栈顶低，则栈顶元素 t 出栈。
        出栈后，右边第一个比它低的柱子是 i，左边第一个比它低的柱子是栈中的 top。
        不断出栈，直到栈为空或当前柱子 i 不比 top 低。
    3.满足 2 之后，当前柱子 i 进栈。

    时间复杂度：O(n)
        每个元素最多进栈一次，出栈一次。
    空间复杂度：O(n)
        需要 O(n) 的空间存储栈。

    参考：https://www.acwing.com/solution/content/140/
*/
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        heights.push_back(-1); // 在数组末尾添加高度-1，使得栈中所有数字在最后出栈

        int res = 0;
        stack<int> stk;
        for (int i = 0; i <= n; i ++) {
            while (!stk.empty() && heights[stk.top()] >= heights[i]) {
                int index = stk.top(); stk.pop();
                if (stk.empty()) {
                    res = max(res, heights[index] * i);
                } else {
                    res = max(res, heights[index] * (i - stk.top() - 1));
                }
            }

            stk.push(i);
        }

        return res;
    }
};

int main() {
    Solution solution;
    vector<int> heights = {2, 1, 5, 6, 2, 3};
    printArray(heights);
    int result = solution.largestRectangleArea(heights);
    cout << "The largest rectangle area is: " << result << endl;

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   栈的使用：
       使用一个栈来存储柱子的索引。
       遍历柱状图的高度数组，对于每个高度：
       如果当前高度小于栈顶柱子的高度，则弹出栈顶柱子，并计算以该柱子为高度的矩形面积。
       更新最大面积。
   面积计算：
       当弹出栈顶柱子时，矩形的宽度为：
           如果栈为空：i（当前索引）。
           如果栈不为空：i - stack[len(stack)-1] - 1。
       矩形的面积为：高度 * 宽度。
   处理边界情况：
       在遍历结束后，栈中可能还有剩余的柱子，需要继续弹出并计算面积。

   时间复杂度：O(n)
       每个柱子最多入栈和出栈一次，因此时间复杂度为 O(n)，其中 n 是柱状图的高度数组长度。
   空间复杂度：O(n)
       使用了一个栈来存储索引，空间复杂度为 O(n)。
*/
// largestRectangleArea 计算柱状图中最大的矩形面积
func largestRectangleArea(heights []int) int {
    n := len(heights)
	stack := []int{}
	maxArea := 0

	for i := 0; i <= n; i ++ {
		height := 0
		if i < n {
			height = heights[i]
		}

		// 当前高度小于栈顶高度时，计算面积
		for len(stack) > 0 && (i == n || heights[stack[len(stack)-1]] > height) {
			h := heights[stack[len(stack)-1]]
			stack = stack[:len(stack)-1] // 弹出栈顶
			width := i
			if len(stack) > 0 {
				width = i - stack[len(stack)-1] - 1
			}
			maxArea = max(maxArea, h * width)
		}

		stack = append(stack, i)
	}

	return maxArea
}

// max 返回两个整数中的较大值
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	// 测试用例
	testCases := []struct {
		heights []int
		expected int
	}{
		{[]int{2, 1, 5, 6, 2, 3}, 10},
		{[]int{2, 4}, 4},
	}

	for i, tc := range testCases {
		result := largestRectangleArea(tc.heights)
		fmt.Printf("Test Case %d, Input: heights = %v\n", i+1, tc.heights)

		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
		}
	}
}