栈， 单调栈
单调栈例题
有N个人，顺次排列，他们的身高分别为H[i]，每个人向自己后方看，他能看到的人是在他后面离他最近的且比他高的人。请依次输出每个人能看到的人的编号Next[i]，如果他后面不存在比他高的人，则输出-1。
想找 "从当前元素向某一方向的第一个 (大于 / 小于) 自己的元素"，就要靠单调栈来维护单调性，对应的是 (递减 / 递增)。
此题维护一个index对应高度单调递减的栈
public class 单调栈 {
public static int[] getHeight(int[] height){
Stack<Integer> stack = new Stack<Integer>();
int[] ans = new int[height.length];
for(int i=0;i<height.length;i++){
while(!stack.isEmpty() && height[stack.peek()]<height[i])
ans[stack.pop()] = i;//如果是高度, 次行是ans[stack.pop()]=height[i];
stack.push(i);
}
while(!stack.isEmpty()) ans[stack.pop()]=-1;
return ans;
}
public static void main(String[] args){
int[] heights1 = {3,2,5,6,1,2};
int[] heights2 = {1,2,3,4,5,6};
int[] heights3 = {6,5,4,3,2,1};
int[] heights4 = {6,1,3,4,2,5};
int[] arr = getHeight(heights4);
for(int i = 0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}
}
}
Largest Rectangle in Histogram
顺着上一题的思路，这题比较暴力的解法可以分为三步：
从左向右扫，寻找对于每个元素，往右能看到的最远距离；
从右向左扫，寻找对于每个元素，往左能看到的远距离；
把两个 arr[] 的结果综合起来，就是从每个位置出发能构造的最大 rectangle.
速度非常慢，只超过了 10.98% ，因为常数项更大。虽然时间复杂度是 O(n)，但是用了 three-pass 才搞定。如果说这种解法有什么优点，就是比较好理解。。是单调栈非常简单直接的应用方式，不加任何 trick.
一次AC
public class Solution {
public int largestRectangleArea(int[] heights) {
int[] left = new int[heights.length];
int[] right = new int[heights.length];
Stack<Integer> rstack = new Stack<Integer>();
for(int i=0;i<heights.length;i++){
while(!rstack.isEmpty() && heights[rstack.peek()]>heights[i])
right[rstack.pop()] = i;
rstack.push(i);
}
while(!rstack.isEmpty()) right[rstack.pop()] = heights.length;
Stack<Integer> lstack = new Stack<Integer>();
for(int i=heights.length-1;i>=0;i--){
while(!lstack.isEmpty() && heights[lstack.peek()]>heights[i])
left[lstack.pop()] = i;
lstack.push(i);
}
while(!lstack.isEmpty()) left[lstack.pop()] = -1;
int maxArea = 0;
for(int i=0;i<heights.length;i++){
maxArea = Math.max(maxArea, (right[i]-left[i]-1) * heights[i]);
}
return maxArea;
}
}
论坛上写法, 复杂的地方太多, 不好记忆
public class Solution {
public int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<Integer>();
int maxArea = 0;
for(int i=0;i<=heights.length;i++){//keypoint1 : i<=heights.length, i is the right board (exclusive self), to parse last histogram
int h = (i==heights.length?0:heights[i]); //keypoint2: when h reach to last histogram, i==heights.length, h = 0
if(stack.isEmpty() || heights[stack.peek()]<=h){//keypoint3: heights[peek]<=h
stack.push(i);
}
else{
int rightidx = i;
int curh = heights[stack.pop()];//keypoint4: curh is heights[stack.pop];
int leftidx = (stack.isEmpty()? -1 : stack.peek());//keypoint5: left board (exclusive selve) is stack.peek() after pop.
maxArea = Math.max(maxArea, (rightidx-leftidx-1)*curh);
i--;//keypoint6: to keep i not change, i-- to balance i++ in for loop.
}
}
return maxArea;
}
}
Increasing Triplet Subsequence
用 LIS 的角度理解的话这题就是无脑套模板。。
不过题目要求 O(n) 时间 O(1) 空间，就得另外动动脑筋了
public class Solution {
public boolean increasingTriplet(int[] nums) {
if(nums == null || nums.length < 3) return false;
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
int index = 0;
for(int i = 1; i < n; i++){
int pos = binarySearch(dp, 0, index, nums[i]);
if(pos > index){
dp[pos] = nums[i];
index = pos;
if(index + 1 >= 3) return true;
}
dp[pos] = Math.min(dp[pos], nums[i]);
}
return false;
}
private int binarySearch(int[] nums, int start, int end, int target){
int left = start;
int right = end;
while(left + 1 < right){
int mid = left + (right - left) / 2;
if(nums[mid] < target){
left = mid;
} else {
right = mid;
}
}
if(target <= nums[left]) return left;
if(target > nums[right]) return right + 1;
return right;
}
}
通过观察这题的具体性质，我们发现在这里我们所谓的 "单调栈" 长度其实是固定的，就是3，等于3了直接返回就行。
因为 3 非常小，我们只需要存两个值，分别代表着单调栈的第一个和第二个位置；当我们碰到第三个位置的情况，就可以返回 true 了。
这个解法的思想也可以推广到任意 k ，k比较小或者为常数的情况，毕竟对于常数 k ，O(k) = O(1).
public class Solution {
public boolean increasingTriplet(int[] nums) {
int min = Integer.MAX_VALUE; int min2 = Integer.MAX_VALUE;
for(int n: nums){
if(n<=min) min = n;
else if(n<=min2) min2 = n;
else return true;
}
return false;
}
}
Russian Doll Envelopes
[[2,100],[3,200],[4,300],[5,500],[5,400],[5,250],[6,370],[6,360],[7,380]]
因为这题，元素之间不存在绝对的大小，不能直接用两个 tuple 去比较，进行 binary search.
两个 tuple [4,300] 和 [5,250] 之间，按理可以说 [4, 300] 更小，但是有可能最优解是由 [5,250] 选出来的。
用LIS中DP的思路, 时间复杂度 O(n^2)
public class Solution {
public int maxEnvelopes(int[][] envelopes) {
if(envelopes==null||envelopes.length==0)
return 0;
int len = envelopes.length;
int[] ans = new int[len+1];
Arrays.sort(envelopes, new Comparator<int[]>(){
public int compare(int[] a, int b[]){
if(a[0]!=b[0])
return a[0]-b[0];
else return a[1]-b[1];
}
});
int max = 1;
for(int i=0;i<len;i++){
ans[i] = 1;
for(int j=i-1;j>=0;j--){
if(envelopes[i][0]>envelopes[j][0] && envelopes[i][1] > envelopes[j][1]){
ans[i] = Math.max(ans[i], ans[j]+1);
}
}
max = Math.max(max, ans[i]);
}
return max;
}
}
正解的流程：
按 [w, h] 中的 w 升序排序；
如果 w 相等，则按照 h 的降序排序(重要！！！)
后面的就和一维 LIS 一样，只考虑 h 的维度做 LIS 就行了。
难点在于，为什么这么做是正确的？
不难看出对于同一个 w 的楼层，我们不能按 h 升序排列，因为会延长自身，导致在同一个 w 上多次套用。
因此对于同一 w 的情况， 要按照 h 降序排列
这样当我们看到一个更大的 h 时，我们可以确定，这一定是一个新的 w，而且根据原来排序的单调性，一定是一个比单调栈内元素都大的新 w，可以套上。
同时对于单调栈中的任意 h，如果 binary search 之后的位置 pos 位于中间，它一定可以套在 pos 之前的所有信封上。如果h小于arr[insert pos], 还可以更新h. 这样做, 不会破坏后面的信封套用, 因为后面看到的信封w一定是大于现在的w. 降低h, 尽可能让后面的信封套上来.
public class Solution {
private class MyComparator implements Comparator<int[]>{
public int compare(int[] a, int[] b){
if(a[0] != b[0]) return (a[0] < b[0]) ? -1: 1;
else return (a[1] < b[1]) ? 1: -1;
}
}
public int maxEnvelopes(int[][] envelopes) {
if(envelopes == null || envelopes.length == 0) return 0;
Arrays.sort(envelopes, new MyComparator());
int n = envelopes.length;
int[] dp = new int[n];
dp[0] = envelopes[0][1];
int index = 0;
for(int i = 1; i < n; i++){
int pos = binarySearch(dp, 0, index, envelopes[i][1]);
if(pos > index){
dp[pos] = envelopes[i][1];
index = pos;
}
dp[pos] = Math.min(dp[pos], envelopes[i][1]);
}
return index + 1;
}
private int binarySearch(int[] dp, int start, int end, int height){
int left = start;
int right = end;
while(left + 1 < right){
int mid = left + (right - left) / 2;
if(height < dp[mid]){
right = mid;
} else {
left = mid;
}
}
if(height <= dp[left]) return left;
if(height > dp[right]) return right + 1;
return right;
}
}
自己写了一个binarysearch版本, 在开始排序的方式以外, 和LIS一模一样, 举一反三.
public class Solution {
public int maxEnvelopes(int[][] envelopes) {
if(envelopes==null||envelopes.length==0)
return 0;
int Len = envelopes.length;
int[] height = new int[Len+1];
Arrays.sort(envelopes, new Comparator<int[]>(){
public int compare(int[] a, int b[]){
if(a[0]!=b[0])
return a[0]-b[0];
else return b[1]-a[1];
}
});
int len = 0;
for(int[] e : envelopes){
int pos = Arrays.binarySearch(height, 0, len, e[1]);
if(pos<0){
pos = -(pos+1);
}
height[pos] = e[1];
if(pos==len)
len++;
}
return len;
}
}
Maximal Rectangle
这道题两个思路, 第一个是用类似于bomb enemy的动态规划的思路, 根据特定情况来更新3个变量, left, right, height, 最后求得max Area.
left(i,j) = max(left(i-1,j), cur_left), cur_left can be determined from the current row
right(i,j) = min(right(i-1,j), cur_right), cur_right can be determined from the current row
height(i,j) = height(i-1,j) + 1, if matrix[i][j]=='1';
height(i,j) = 0, if matrix[i][j]=='0'
需要注意的是matrix[i][j]==0时, left=-1, right=n, height=0. 为什么不将left和right设为当前的j, 这么做是不为了不影响下一行(row)的计算.
public class Solution { public int maximalRectangle(char[][] matrix) { if(matrix==null || matrix.length==0 || matrix[0].length==0) return 0; int m = matrix.length; int n = matrix[0].length; int[] heights = new int[n]; int[] left = new int[n]; Arrays.fill(left, -1); int[] right = new int[n]; Arrays.fill(right, n); int globalMax = 0; for(int i=0;i<m;i++){ int curleft = -1; int curright= n; for(int j=0;j<n;j++){ if(matrix[i][j]=='1') heights[j]++; else heights[j]=0; } for(int j=0;j<n;j++){ if(matrix[i][j]=='1') left[j] = Math.max(left[j], curleft); else{ left[j] = -1; curleft=j; } } for(int j=n-1;j>=0;j--){ if(matrix[i][j]=='1') right[j] = Math.min(right[j], curright); else{ right[j] = n; curright=j; } } for(int j=0;j<n;j++){ int localMax = (right[j]-left[j]-1)*heights[j]; globalMax = Math.max(localMax, globalMax); } } return globalMax; } }
第二个是用类似于Largest Rectangle Area的思路, 将每一行看成求当前histogram组成的largest rectangle area. 一次AC
public class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix==null || matrix.length==0 || matrix[0].length==0) return 0;
int m = matrix.length; int n = matrix[0].length;
int[] heights = new int[n];
int globalMax = 0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]=='1') heights[j]++;
else heights[j]=0;
}
int localMax = largestRectangleArea(heights);
globalMax = Math.max(globalMax, localMax);
}
return globalMax;
}
Sliding Window Maximum
操作特点：
只关心区域内的 max;
只要同一区域内 max 一样，输出就一样，不在意元素的出现顺序，因此这题有别于 max/min stack 的保存元素顺序要求。
这题暴力循环可以 O(nk)，hasheap 可以 O(n log k)，deque 可以 O(n).
我们每一步要执行下面三个操作：
- 添加当前元素 nums[i];
- 删除指定元素 nums[i - k];
- 找到当前 window max;
暴力解法中，我们可以直接维护一个 list，每次操作都进行扫描，这样的复杂度是：
- Add O(1)
- Remove O(k)
- max O(k)
另一种选择是，维护一个 sorted list，这样的复杂度是：
- Add O(k)
- Remove O(k)
- max O(1)
再观察题目特性可以发现，我们在维护 sorted list 上有很多可以取巧的地方：
- 因为我们只关心每个 window 上的 max，因此没有必要把 window 内的所有元素都留着，在 Add 的时候可以直接把小于新元素的值都 pop 掉；
- 而在 remove 上，对最终结果会产生影响的，只有我们 remove 的元素就是 max 的情形，因为其他无关元素在 add 的时候就被拿掉了；因此我们可以存一个元素的相对位置，以此来判断我们要删掉的元素是不是当前的 max.
- 因为我们维护的是 sorted array ，max 依然是 O(1).
- 由于每一个元素只会被 add 和 remove 一次，整个流程的均摊复杂度就是 O(1).
要点：
维护一个可以双向操作的 sorted array. 单调递减的, peek永远是当前最大元素的index.
Deque 里面要存 index，而不是值，不然会出现 [8,1,2,8...] 这种情况下，我们有可能会把刚加进去的 8 又给拿出来的 bug.
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums==null||nums.length==0)
return new int[0];
LinkedList<Integer> deque = new LinkedList<Integer>();
int[] res = new int[nums.length-k+1];
for(int i=0;i<nums.length;i++){
if(!deque.isEmpty() && deque.peekFirst() == i-k)
deque.poll();
while(!deque.isEmpty() && nums[deque.peekLast()]<nums[i])
deque.removeLast();
deque.offer(i);
if(i+1>=k){
res[i+1-k] = nums[deque.peekFirst()];
}
}
return res;
}
}
这里我自己的写法是通过hashmap来存需要移除的数字, 当priorityqueue的top元素是hashmap中存在的, 则需要移除. 开始用了hashset, 这里忽略了可能存在重复数字, 比如[8,0,0, 8], 用hashset会将两个8都移除.
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length==0) return new int[0];
int[] ans = new int[nums.length-k+1];
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int right=0;
for(;right<k-1;right++) pq.offer(nums[right]);
for(int left=0;right<nums.length;right++, left++){
pq.offer(nums[right]);
ans[left] = pq.peek();
map.put(nums[left], map.getOrDefault(nums[left], 0)+1);
while(map.containsKey(pq.peek()) && map.get(pq.peek())>0){
map.put(pq.peek(), map.get(pq.peek())-1);
pq.poll();
}
}
return ans;
}
}
Remove K Digits
create maximum number的弱化版，删除k个数字等于maintain n－k个数字。按照套路来就可以。
注意：在stack大小已知的情况下，stack可以用数组来代替，只要记得通过尾index来读写就可以。
注意：string 字符为“ ”的时候需要“0”
public class Solution {
public String removeKdigits(String num, int k) {
char[] arr = num.toCharArray(); int keep = arr.length-k;
char[] ans = new char[keep]; int len = 0;
for(int i=0;i<arr.length;i++){
while(len>0&&len+arr.length-i>keep&&ans[len-1]>arr[i])
len--;
if(len<keep)
ans[len++] = arr[i];
}
int i=0;
for(;i<keep&&ans[i]=='0';i++) ;
StringBuilder sb = new StringBuilder();
while(i<keep) sb.append(ans[i++]);
return sb.length()==0?"0":sb.toString();
}
}
Create Maximum Number
自己照着思路写的，结果 跑到88的cases TLE了。复杂度是一样的。
枚举第一个数组A的个数i，那么数组B的个数就确定了 k -i。
然后枚举出A和B长度分别为i和k-i的最大子数组，（可以用栈，类似leetcode Remove Duplicate Letters）
最后组合看看哪个大。
组合的过程类似合并排序，看看哪个数组大，就选哪个。
枚举数组长度复杂度O(k)，找出最大子数组O(n)，合并的话O(k^2)
而k最坏是m+n,所以总的复杂度就是O((m+n)^3)
public class Solution {
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int[] ans = new int[k];
for(int i=Math.max(k-nums2.length,0);i<=k&&i<=nums1.length;i++){
int[] arr1 = select(nums1, i);
int[] arr2 = select(nums2, k-i);
int[] cur = merge(arr1, arr2);
if(compare(cur, 0,ans,0)) ans = cur;
}
return ans;
}
public int[] select(int[] nums1, int k){
Stack<Integer> stack = new Stack<Integer>();
for(int i=0;i<nums1.length;i++){
while(!stack.isEmpty()&&stack.size()+nums1.length-i>k&&stack.peek()<nums1[i])
stack.pop();
if(stack.size()<k)
stack.push(nums1[i]);
}
int[] ans = new int[k];
for(int i=k-1;i>=0;i--){
ans[i]=stack.pop();
}
return ans;
}
public int[] merge(int[] arr1, int[] arr2){
int n1 = arr1.length; int n2 = arr2.length;
System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
int[] ans = new int[n1+n2];
for(int i=0, p1=0, p2 =0;i<ans.length;){
if(p1<n1&&p2<n2){
ans[i++] = compare(arr1, p1, arr2, p2)?arr1[p1++]:arr2[p2++];
}
else if(p2<n2)
ans[i++] = arr2[p2++];
else if(p1<n1)
ans[i++] = arr1[p1++];
System.out.println(ans[i-1]);
}
return ans;
}
public boolean compare(int[] nums1, int start1, int[] nums2, int start2) {
for (; start1 < nums1.length && start2 < nums2.length; start1++, start2++) {
if (nums1[start1] > nums2[start2]) return true;
if (nums1[start1] < nums2[start2]) return false;
}
return start1 != nums1.length;
}
}