-
Notifications
You must be signed in to change notification settings - Fork 2
Rectangle Series Questions
https://leetcode.com/problems/largest-rectangle-in-histogram/description/
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. For example, Given heights = [2,1,5,6,2,3], return 10.
Solution
Solution 1: 中心开花。（在每一个点，向左，向右找左右极限边界，然后计算面积。）
Solution 2: Stack Idea是 set up a stack。Stack存idx，是个单调递增的stack。因为是单调递增的，我们知道每一个点的height，左边界（该点弹出后peek()得到的idx ＋ 1）。
此时，问题转化成，哪一个是右边界。右边界发生在，当新遇到的点的height小于stack.peek（）的高度，即右边界是curIdx － 1. 此时开始弹出stack中的点计算面积。
注意的地方
- stack中要存的是idx。 需要比较的是heights[cur] >= hieghts[stack.peek()]
- 考虑stack为空的情况
- 当不断弹出，stack为空时，left边界应该是0.
- 我们需要在最后加一个－1点，使右边缘的concer case得到考虑。
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. (https://leetcode.com/problems/trapping-rain-water/description/)
Solution 1
中心开花，对于每个点，向左看找最高的，向右找最大的。DP可以帮助我们找到每个点上左右最大值。然后求和。
Solution 2
无需array，需要left, right, leftMaxVal, rightMaxVal 变量，比较leftMaxVal, rightMaxVal，谁小移谁，相向而行，求和。 之所以谁小移谁，是因为我们只care最小的边界，未知区域内即使有很高的边界也无需care。
###407. Trapping Rain Water II###
https://leetcode.com/problems/trapping-rain-water-ii/description/
Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.
Note: Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.
Solution 用prirotyQueue把边界的cell存起来，每次弹出一个找四周未访问点，sum去加高度差，然后把该点的height(该店高度或水高度）加入priorityQueue。