Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Example:
Input: [1,8,6,2,5,4,8,3,7] Output: 49
受制於比較矮的那一邊
The shorter line's pointer might find higher line to overcome the reduction in area caused by the width reduction.
public int maxArea(int[] height) {
int i=0, j=height.length-1;
int max = Integer.MIN_VALUE;
while(i<j){
if(height[i] < height[j]){
max = Math.max(max, height[i]*(j-i));
i++;
}else{
max = Math.max(max, height[j]*(j-i));
j--;
}
}
return max;
42 Trapping Rain Water
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.
DP
Record the highest point so far from left to right and right to left.
def trap(self, height: List[int]) -> int:
l, r, s = 0, len(height)-1, 0
lMax, rMax = 0, 0
while l<r:
if height[l] < height[r]:
if height[l] < lMax: s += lMax - height[l]
else: lMax = height[l]
l+=1
else:
if height[r] < rMax: s += rMax - height[r]
else: rMax = height[r]
r-=1
return s
407. Trapping Rain Water II
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.
Example
[
[1,4,3,1,3,2],
[3,2,1,3,2,4],
[2,3,3,2,3,1]
]
Return 4
Greedy + minHeap
Put boundary heights in minHeap, starting from the lowest boundary
Update current height, traverse 4 directions
Add to answer whenever we can see nextHeight < currentHeight
from heapq import *
class Solution:
def trapRainWater(self, heightMap: List[List[int]]) -> int:
m, n = len(heightMap), len(heightMap[0])
maxHeight = float('-inf')
visit = set()
heap = []
ans = 0
for i in (0, m-1):
for j in range(n):
heappush(heap, (heightMap[i][j], i, j))
visit.add((i, j))
for j in (0, n-1):
for i in range(1, m-1):
heappush(heap, (heightMap[i][j], i, j))
visit.add((i, j))
while heap:
height, x, y = heappop(heap)
maxHeight = max(maxHeight, height)
for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
nx, ny = x + dx, y + dy
if not (0 <= nx < m and 0 <= ny < n): continue
if (nx, ny) in visit: continue
visit.add((nx, ny))
nextHeight = heightMap[nx][ny]
if maxHeight > nextHeight:
ans += maxHeight - nextHeight
heappush(heap, (nextHeight, nx, ny))
return ans
768. Max Chunks To Make Sorted II
769 with duplicate number
Store the max from left and store the min from left
A pivot point is at the point minRight[i+1] >= maxMin[i]
public int maxChunksToSorted(int[] arr) {
int len = arr.length;
int[] maxLeft = new int[len];
int[] minRight = new int[len];
maxLeft[0] = arr[0];
for(int i=1; i<len; i++){
maxLeft[i] = Math.max(maxLeft[i-1], arr[i]);
}
minRight[len-1] = arr[len-1];
for(int i=len-2; i>=0; i--){
minRight[i]= Math.min(minRight[i+1], arr[i]);
}
int count =1;
for(int i=0; i<len-1; i++){
if(minRight[i+1] >= maxLeft[i]) count++;
}
return count;
}
769. Max Chunks To Make Sorted
Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], split the array into chunks, and individually sort each chunk. After concatenating them, the result equals the sorted array.
What is the most number of chunks we could have made?
Use index as sorted answer array to match the current array
Take the max number as pivot point
public int maxChunksToSorted(int[] arr) {
/** index 0, 1, 2, 3, 4
* max 1, 1, 2, 3, 4 return 4
*
* index 0, 1, 2, 3, 4
* max 4, 4, 4, 4, 4 return 1
*/
int count = 0;
int max = arr[0];
for(int i=0; i< arr.length; i++){
max = Math.max(max, arr[i]);
if(max == i) count++;
}
return count;
}