算法leetcode｜84. 柱状图中最大的矩形（rust重拳出击）

---

---

84. 柱状图中最大的矩形：

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

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

样例 1：

输入：

	heights = [2,1,5,6,2,3]
	
输出：
	
	10
	
解释：
	
	最大的矩形为图中红色区域，面积为 10
1
2
3
4
5
6
7
8
9
10
11

样例 2：

输入：
	
	 heights = [2,4]
	 
输出： 
	
	4
1
2
3
4
5
6
7

提示：

• 1 <= heights.length <=10⁵
• 0 <= heights[i] <= 10⁴

---

分析：

• 面对这道算法题目，二当家的再次陷入了沉思。
• 眼睛一看似乎有思路，但是一动手就容易不知如何下手。
• 双循环，遍历每个柱子，查找左边第一个低于自己的柱子，和右边第一个低于自己的柱子，这样就能算出当前柱子这个高度最大的宽度，有搞头，很明显会很慢，还有没有更好的办法呢。
• 找到每个柱子的左右边界（第一个低于自己的柱子）是关键，有没有办法降低查找的复杂度呢？
• 要是能一次遍历就把左右边界找到就好了，祭出神器单调栈，如果栈为空就入栈（这里可以使用技巧，让处理逻辑统一），否则判断下一个柱子如果高于栈顶或者和栈顶一样高也直接入栈，如果低于栈顶就出栈，因为当前这个柱子就是栈顶元素的右边界，重复这个过程，就可以在一次遍历的过程中就找到左右边界。
• 特别要注意遍历过程中栈为空，和遍历完所有柱子但是栈不为空的情况。

---

题解：

rust：

impl Solution {
    pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
        let mut ans = 0;

        let mut stack = vec![-1];
        let n = heights.len();
        (0..n).for_each(|i| {
            while stack.len() > 1 && heights[*stack.last().unwrap() as usize] > heights[i] {
                // 栈中比当前位置高的那些待确定右边界的下标都可以确定右边界了

                ans = ans.max(heights[stack.pop().unwrap() as usize] * (i as i32 - 1 - stack.last().unwrap()));
            }
            // 入栈，等到能够确定右边界时处理
            stack.push(i as i32);
        });

        while stack.len() > 1 {
            // 栈中剩余的都是右边没有更低的

            ans = ans.max(heights[stack.pop().unwrap() as usize] * (n as i32 - 1 - stack.last().unwrap()));
        }

        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

go：

func largestRectangleArea(heights []int) int {
    max := func(x, y int) int {
		if x > y {
			return x
		}
		return y
	}

	ans := 0

	n := len(heights)
	stack := []int{-1}
	for i := 0; i < n; i++ {
		for len(stack) > 1 && heights[stack[len(stack)-1]] > heights[i] {
			// 栈中比当前位置高的那些待确定右边界的下标都可以确定右边界了

			ans = max(ans, heights[stack[len(stack)-1]]*(i-1-stack[len(stack)-2]))
			// 出栈
			stack = stack[:len(stack)-1]
		}
		// 入栈，等到能够确定右边界时处理
		stack = append(stack, i)
	}

	for len(stack) > 1 {
		// 栈中剩余的都是右边没有更低的

		ans = max(ans, heights[stack[len(stack)-1]]*(n-1-stack[len(stack)-2]))
		// 出栈
		stack = stack[:len(stack)-1]
	}

	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

---

c++：

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int ans = 0;

        const int n = heights.size();
        stack<int> s;
        s.push(-1);
        for (int i = 0; i < n; ++i) {
            while (s.size() > 1 && heights[s.top()] > heights[i]) {
                // 栈中比当前位置高的那些待确定右边界的下标都可以确定右边界了

                int height = heights[s.top()];
                s.pop();
                ans = max(ans, height * (i - 1 - s.top()));
            }
            // 入栈，等到能够确定右边界时处理
            s.push(i);
        }

        while (s.size() > 1) {
            // 栈中剩余的都是右边没有更低的

            int height = heights[s.top()];
            s.pop();
            ans = max(ans, height * (n - 1 - s.top()));
        }

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---

python：

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        ans = 0

        n = len(heights)
        stack = [-1]
        for i in range(n):
            while len(stack) > 1 and heights[stack[-1]] > heights[i]:
                # 比当前位置高的那些待确定右边界的下标都可以确定右边界了
                ans = max(ans, heights[stack.pop()] * (i - 1 - stack[-1]))
            # 入栈，等到能够确定右边界时处理
            stack.append(i)
        while len(stack) > 1:
            # 栈中剩余的都是右边没有更低的
            ans = max(ans, heights[stack.pop()] * (n - 1 - stack[-1]))

        return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

java：

class Solution {
    public int largestRectangleArea(int[] heights) {
        int ans = 0;

        final int      n     = heights.length;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1);
        for (int i = 0; i < n; ++i) {
            while (stack.size() > 1 && heights[stack.peek()] > heights[i]) {
                // 栈中比当前位置高的那些待确定右边界的下标都可以确定右边界了

                ans = Math.max(ans, heights[stack.pop()] * (i - 1 - stack.peek()));
            }
            // 入栈，等到能够确定右边界时处理
            stack.push(i);
        }

        while (stack.size() > 1) {
            // 栈中剩余的都是右边没有更低的

            ans = Math.max(ans, heights[stack.pop()] * (n - 1 - stack.peek()));
        }

        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

---

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~

---