公司新闻

算法leetcode|84. 柱状图中最大的矩形(rust重拳出击)

文章目录



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

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

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

样例 1:

输入:

	heights = [2,1,5,6,2,3]
	
输出:
	
	10
	
解释:
	
	最大的矩形为图中红色区域,面积为 10

样例 2:

输入:
	
	 heights = [2,4]
	 
输出: 
	
	4

提示:

  • 1 <= heights.length <=105
  • 0 <= heights[i] <= 104

分析:

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

题解:

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;
    }
}

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
}

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;
    }
};

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


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;
    }
}

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