class MinStack {
Stack<Integer> stk, minStk;
/** initialize your data structure here. */
public MinStack() {
stk = new Stack<>();
minStk = new Stack<>();
}
public void push(int x) {
stk.push(x);
if (minStk.isEmpty() || minStk.peek() >= x) {
minStk.push(x);
}
}
public void pop() {
int val = stk.pop();
if (minStk.peek() == val) {
minStk.pop();
}
}
public int top() {
return stk.peek();
}
public int getMin() {
return minStk.peek();
}
}
Max Stack
brute force solution---Interview friendly
3 stacks, stk, maxStk and buffer inside of popMax()
size of stk and maxStk is always same
class MaxStack {
/** initialize your data structure here. */
Stack<Integer> stk, maxStk;
public MaxStack() {
//brute force solution
//3 stacks, stk, maxStk and buffer inside of popMax()
//size of stk and maxStk is always same
stk = new Stack<>();
maxStk = new Stack<>();
}
public void push(int x) {
int max = maxStk.isEmpty() ? x : maxStk.peek();
maxStk.push(x > max ? x : max);
stk.push(x);
}
public int pop() {
maxStk.pop();
return stk.pop();
}
public int top() {
return stk.peek();
}
public int peekMax() {
return maxStk.peek();
}
public int popMax() {
int max = peekMax();
Stack<Integer> buffer = new Stack<>();
while(top() != max) {
buffer.push(pop());
}
pop();
while (!buffer.isEmpty()) {
push(buffer.pop());
}
return max;
}
}
Optimize to not use maxStk, use a max variable instead
Largest Rectangle in Histogram
如何构成rectangle
given index i, 找到i左边的第一个小于nums[i]的值，右边的第一个小于nums[i]的值
class Solution {
/*
brute force
2 for loops
O(N^2) time
Improved
h = heights[stk.peek()]
l = 左边第一个比h小的height的idx
r = i, 左边第一个比h小的height的idx, if heights[i]< h
w = i - l - 1
area = h * w
*/
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) return 0;
Stack<Integer> stk = new Stack<>(); //monontonic increasing stk, idx
int max = 0;
int n = heights.length;
for (int i = 0; i <= n; i++) {
int curHeight = i == n ? -1 : heights[i];
while (!stk.isEmpty() && curHeight < heights[stk.peek()]) {
int h = heights[stk.pop()];
int w = stk.isEmpty() ? i : i - stk.peek() - 1;
max = Math.max(max, h * w);
}
stk.push(i);
}
return max;
}
}
Next greater element类问题，经典的单调栈应用
Next greater element I
Next greater element II
Next greater node in Linked List
Daily Temperature
Next Greater Element I
给两个数组，nums1和nums2, nums1 是nums2 的子集
要求返回nums1里每一个数在nums2里的next greater element
典型的单调栈问题
从右向左遍历nums2, 维护单调递减栈
always compare nums2[i] with stk.peek()
if nums[i] < stk.peek() then arr[i] == stk.peek()
else stk.pop(), try again until stk.isEmpty()
原始版本代码
class Solution {
/*
从右向左遍历nums2, 维护单调递减栈
并建立新的arr to store nextGreater element for each element in nums[i]
always nums2[i] with stk.peek()
if nums[i] < stk.peek() then arr[i] == stk.peek()
else stk.pop(), try again until stk.isEmpty()
*/
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer, Integer> nextGreaterElements = new HashMap<>();
Stack<Integer> minStk = new Stack<>();
for (int i = nums2.length - 1; i >= 0; i--) {
int num = nums2[i];
while(!minStk.isEmpty()) {
if(num < minStk.peek()) {
nextGreaterElements.put(num, minStk.peek());
minStk.push(num);
break;
} else {
minStk.pop();
}
}
if (minStk.isEmpty()) {
nextGreaterElements.put(num, -1);
minStk.push(num);
}
}
int[] res = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
res[i] = nextGreaterElements.get(nums1[i]);
}
return res;
}
}
优化后的clean code
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer, Integer> nextGreaterElements = new HashMap<>();
Stack<Integer> minStk = new Stack<>();
for (int i = nums2.length - 1; i >= 0; i--) {
int num = nums2[i];
while (!minStk.isEmpty() && num > minStk.peek()) {
minStk.pop();
}
nextGreaterElements.put(num, minStk.isEmpty() ? -1 : minStk.peek());
minStk.push(num);
}
int[] res = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
res[i] = nextGreaterElements.get(nums1[i]);
}
return res;
}
Next Greater Element II
给定一个nums, 求nums里每一个数的next greater element
nums is circular array
跟第一题相同的思路，但是需要iterate 2 loops, i from 2 * n - 1 to 0
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] next = new int[n];
Stack<Integer> stk = new Stack<>(); //stack, 单调递减
for (int i = n * 2 - 1; i >= 0; i--) {
int num = nums[i % n];
while (!stk.isEmpty() && num >= stk.peek()) {
stk.pop();
}
if (i < n) {
next[i] = stk.isEmpty() ? -1 : stk.peek();
}
stk.push(num);
}
return next;
}
Next Greater Node in Linked List
首先convert linked list to array, 然后就是典型的find next greater element的问题
求右边第一个比当前数大的值->单调递减栈
class Solution {
public int[] nextLargerNodes(ListNode head) {
int[] arr = toArray(head);
Deque<Integer> stk = new ArrayDeque<>(); //store index of arr, arr[index] descending order
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
while (!stk.isEmpty() && arr[i] > arr[stk.peek()]) {
res[stk.pop()] = arr[i];
}
stk.push(i);
}
return res;
}
private int[] toArray(ListNode head) {
List<Integer> list = new ArrayList<>();
while (head != null) {
list.add(head.val);
head = head.next;
}
int size = list.size();
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = list.get(i);
}
return arr;
}
}