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即双端队列。比较难想到。

做法是:先考虑用stack,就是每次扫到新node时,先看stack.peek是不是比node小,如果小得话就把peek pop出去。直到peek比node小时,把node push进stack

然后此题因为需要每当slide window时,要把第一个数remove掉,这就需要用到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++) {
        addElement(deque, i, nums);
    }
    result.add(nums[deque.peekFirst()]);
    for (int i = 1; i < nums.length + 1 - k; i++) {
        removeElement(deque, i - 1);
        addElement(deque, i + k - 1, nums);
        result.add(nums[deque.peekFirst()]);
    }
    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();
    }
}

 

FacebookTwitterGoogle+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.

用7,3,8,2,4,5走一遍就理解了

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.

histogram

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

histogram

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]))

注意:凡是求左边第一个比它小得数这类问题 用stack 存数组的index

策略是:

如果新来的数大于A[stack.peek()], 直接push i to stack, otherwise stack.pop()直到找到第一个比他小得数停下,push i to stack.

这样对一个array来说 只要走一遍就知道每一个数的左边第一个比它小的数是哪个。

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();
    }
}