# Sliding Window Maximum

#### Sliding Window Maximum

Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration from the start of the array, find the maximum number inside the window at each moving.

Example

For array `[1, 2, 7, 7, 8]`, moving window size `k = 3`. return `[7, 7, 8]`

At first the window is at the start of the array like this

`[|1, 2, 7| ,7, 8]` , return the maximum `7`;

then the window move one step forward.

`[1, |2, 7 ,7|, 8]`, return the maximum `7`;

then the window move one step forward again.

`[1, 2, |7, 7, 8|]`, return the maximum `8`;

Challenge

o(n) time and O(k) memory

Solution:

1. 首先这道题最容易想到得是用heap做，维护一个heap，但是sliding window需要删除node，于是如果用HashHeap的话可以将时间复杂度降到O(nlogn). 即每次slide一次用logn时间添加结点再用logn时间删除结点。

2. 第二个方法是线性的 需要用到Deque即双端队列。比较难想到。

```public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
ArrayList<Integer> result = new ArrayList<>();
if (nums == null || nums.length == 0 || nums.length < k) {
return result;
}
Deque<Integer> deque = new ArrayDeque<>();
deque.offerLast(0);
for (int i = 1; i < k; i++) {
}
for (int i = 1; i < nums.length + 1 - k; i++) {
removeElement(deque, i - 1);
addElement(deque, i + k - 1, nums);
}
return result;
}
//when adding a new element i,
//if nums[i]>=peakLast, we should keep popping the peak until the peak <nums[i]
//then we push nums[i]
public void addElement(Deque<Integer> deque, int index, int[] nums) {
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[index]) {
//pop the peak element
deque.pollLast();
}
deque.offerLast(index);
}

//when removing element, only check if the first of the deck is the same index
//then remove it. It is likely that it has already been popped out of the deque.
public void removeElement(Deque<Integer> deque, int index) {
if (index == deque.peekFirst()) {
deque.pollFirst();
}
}```

Share

# Max Tree

#### Max Tree

Given an integer array with no duplicates. A max tree building on this array is defined as follow:

• The root is the maximum number in the array
• The left subtree and right subtree are the max trees of the subarray divided by the root number.

Construct the max tree by the given array.

Example

Given `[2, 5, 6, 0, 3, 1]`, the max tree constructed by this array is:

```<code>    6
/ \
5   3
/   / \
2   0   1
</code>```
Challenge

O(n) time and memory.

Solution: 用stack来维护在每个数出现前比它大得数。

When new node comes in, if it is larger than the peek, stack.pop() and at the same time append it as the new node’s left child. until the stack peek is larger than the new node or the stack is empty, at this time, the peek.right = new node. then we push new node into the stack. if the stack is empty when the new node is pushed, the new node is the temporary root.

```public TreeNode maxTree(int[] A) {
if (A == null || A.length == 0) {
return null;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode root = null;
for (int i = 0; i < A.length; i++) {
TreeNode curr = new TreeNode(A[i]);
while (!stack.isEmpty() && A[i] >= stack.peek().val) {
TreeNode tmp = stack.pop();
tmp.right = curr.left;
curr.left = tmp;
}
if (!stack.isEmpty()) {
stack.peek().right = curr;
} else {
root = curr;
}
stack.push(curr);
}
return root;
}```

# Largest Rectangle in Histogram

Largest Rectangle in Histogram

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.

Above is a histogram where width of each bar is 1, given height = `[2,1,5,6,2,3]`.

The largest rectangle is shown in the shaded area, which has area = `10` unit.

Example

Given height = `[2,1,5,6,2,3]`,
return `10`.

Solution: max(the area of rectangle which height[i] is the shortest bar)

leftBound[i]: index of the first element less than height[i] starting from the left +1

rightBound[i]: index of the first element less than height[i] starting from the right -1

result = max(height[i]*(rightBound[i]-leftBound[i]))

O(n) time.

Solution 1. Straightforward Version

```public int largestRectangleArea(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int[] leftBound = new int[height.length];
int[] rightBound = new int[height.length];
Stack<Integer> minStack = new Stack<>();
for (int i = 0; i < height.length; i++) {
while (!minStack.isEmpty() && height[i] <= height[minStack.peek()]) {
minStack.pop();
}
if (minStack.isEmpty()) {
leftBound[i] = 0;
} else {
leftBound[i] = minStack.peek() + 1;
}
minStack.push(i);
}
minStack = new Stack<>();
for (int i = height.length - 1; i >= 0; i--) {
while (!minStack.isEmpty() && height[i] <= height[minStack.peek()]) {
minStack.pop();
}
if (minStack.isEmpty()) {
rightBound[i] = height.length - 1;
} else {
rightBound[i] = minStack.peek() - 1;
}
minStack.push(i);
}
int maxArea = 0;
for (int i = 0; i < height.length; i++) {
int area = height[i] * (rightBound[i] - leftBound[i] + 1);
maxArea = Math.max(maxArea, area);
}
return maxArea;
}```

Solution 2. Fancy Version, One pass

```public int largestRectangleArea(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
Stack<Integer> minStack = new Stack<>();
int maxArea = 0;
for (int i = 0; i <= height.length; i++) {
int curr = (i == height.length) ? -1 : height[i];
while (!minStack.isEmpty() && curr <= height[minStack.peek()]) {
int tmp = minStack.pop();
int left = minStack.isEmpty() ? 0 : minStack.peek() + 1;
int area = (i - left) * height[tmp];
maxArea = Math.max(area, maxArea);
}
minStack.push(i);
}
return maxArea;
}```

# Min Stack

#### Min Stack

Implement a stack with min() function, which will return the smallest number in the stack.

It should support push, pop and min operation all in O(1) cost.

Example

Operations: push(1), pop(), push(2), push(3), min(), push(1), min() Return: 1, 2, 1

Note

min operation will never be called if there is no number in the stack

Solution: 用一个minStack维护最小值，保存每一个状态的最小值。当新来的数比当前的栈顶小的时候，也就是说这个数是最小值，push to minStack，pop的时候要看pop的这个数是不是和minStack的栈顶一样，也就是这个数是最小数，stack.pop()的同时要minStack.pop(). 注意duplicates numbers, 所以push一个和当前最小数一样大的数时，也需要push to minStack.

```public class Solution {
Stack<Integer> minStack;
Stack<Integer> stack;
public Solution() {
stack = new Stack<>();
minStack = new Stack<>();
}

public void push(int number) {
stack.push(number);
if(minStack.isEmpty()){
minStack.push(number);
}else{
if(minStack.peek()>=number){
minStack.push(number);
}
}
}

public int pop() {
if(stack.peek().equals(minStack.peek())){
minStack.pop();
}
return stack.pop();
}

public int min() {
return minStack.peek();
}
}```