单调栈例题
有N个人，顺次排列，他们的身高分别为H[i]，每个人向自己后方看，他能看到的人是在他后面离他最近的且比他高的人。请依次输出每个人能看到的人的编号Next[i]，如果他后面不存在比他高的人，则输出-1。
想找 "从当前元素向某一方向的第一个 (大于 / 小于) 自己的元素"，就要靠单调栈来维护单调性，对应的是 (递减 / 递增)。
public class Main {
public static int[] getHeight(int[] heights){
int n = heights.length;
int[] arr = new int[n];
// Stack stores index of people
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < n; i++){
while(!stack.isEmpty() && heights[stack.peek()] <= heights[i]){
arr[stack.pop()] = i;
}
stack.push(i);
}
while(!stack.isEmpty()){
arr[stack.pop()] = -1;
}
return arr;
}
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] + " ");
}
}
}
顺着上一题的思路，这题比较暴力的解法可以分为三步：
从左向右扫，寻找对于每个元素，往右能看到的最远距离；
从右向左扫，寻找对于每个元素，往左能看到的远距离；
把两个 arr[] 的结果综合起来，就是从每个位置出发能构造的最大 rectangle.
速度非常慢，只超过了 1.27% ，因为常数项更大。虽然时间复杂度是 O(n)，但是用了 three-pass 才搞定。如果说这种解法有什么优点，就是比较好理解。。是单调栈非常简单直接的应用方式，不加任何 trick.
public class Solution {
public int largestRectangleArea(int[] heights) {
int[] right = findToRight(heights);
int[] left = findToLeft(heights);
int max = 0;
for(int i = 0; i < heights.length; i++){
max = Math.max(max, (right[i] - left[i] + 1) * heights[i]);
}
return max;
}
private int[] findToRight(int[] heights){
int[] right = new int[heights.length];
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < heights.length; i++){
while(!stack.isEmpty() && heights[stack.peek()] > heights[i]){
right[stack.pop()] = i - 1;
}
stack.push(i);
}
while(!stack.isEmpty()){
int index = stack.pop();
right[index] = heights.length - 1;
}
return right;
}
private int[] findToLeft(int[] heights){
int[] left = new int[heights.length];
Stack<Integer> stack = new Stack<>();
for(int i = heights.length - 1; i >= 0; i--){
while(!stack.isEmpty() && heights[stack.peek()] > heights[i]){
left[stack.pop()] = i + 1;
}
stack.push(i);
}
while(!stack.isEmpty()){
int index = stack.pop();
left[index] = 0;
}
return left;
}
}
用 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) {
if(nums == null || nums.length < 3) return false;
int n = nums.length;
int num1 = Integer.MAX_VALUE;
int num2 = Integer.MAX_VALUE;
for(int i = 0; i < n; i++){
if(nums[i] <= num1){
num1 = nums[i];
} else if(nums[i] <= num2){
num2 = nums[i];
} else {
return true;
}
}
return false;
}
}
[[2,100],[3,200],[4,300],[5,500],[5,400],[5,250],[6,370],[6,360],[7,380]]
这题试着用 LIS 的写法思路写了一下，然而卡在了这个 test case 上。
因为这题，元素之间不存在绝对的大小，不能直接用两个 tuple 去比较，进行 binary search.
两个 tuple [4,300] 和 [5,250] 之间，按理可以说 [4, 300] 更小，但是有可能最优解是由 [5,250] 选出来的。
正解的流程：
如果 w 相等，则按照 h 的降序排序(重要！！！)
后面的就和一维 LIS 一样，只考虑 h 的维度做 LIS 就行了。
难点在于，为什么这么做是正确的？
不难看出对于同一个 w 的楼层，我们不能按 h 升序排列，因为会延长自身，导致在同一个 w 上多次套用。
这样当我们看到一个更大的 h 时，我们可以确定，这一定是一个新的 w，而且根据原来排序的单调性，一定是一个比单调栈内元素都大的新 w，可以套上。
同时对于单调栈中的任意 h，如果 binary search 之后的位置 pos 位于中间，它一定可以套在 pos 之前的所有信封上。
速度超过 87.50%，还不错。
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;
}
}