Daily Archives: October 16, 2015

Get max histogram rectangle

I solved this problem one year ago. This time I solved it again and wrote some analysis for it.

Problem definition:
Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the width is 1 unit.

For example, consider the following histogram with 6 bars of heights {6, 2, 5, 4, 5, 6}. The largest possible rectangle possible is 12 (see the below figure, the max area rectangle is highlighted in red)
histogram1

I think this problem has some application background. That is for each number in set of numbers, find farthest continuous left and right of numbers which all larger than the number. For example, for element 3, the right most it can reach is 4, the left most it can reach is element 2.

To solve this problme, stach is used. We should firstly iterate number from left to right by stack by below rules:
1.From left to right
2.If current is smaller than stack top, then pop stack. After pop stack tp, calculate area size for position tp
3.In the end, push current index

Then we pop all element in stack:
1. For each poped element, use arrary.length and stack.peek() to calculate area size.

The process is like below:
From left to right
historgram2

Pop the rest stack
histogram3

github: link

Longest valid parentheses

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring

For “(()”, the longest valid parentheses substring is “()”, which has length = 2.
Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

Below are the 2 ways how I implemented it.
For getMaxParentheses2(), it always stores element into stack. When there is a pop function, it will calculate the size by curr_pos and peek() for the length.
For getMaxParentheses(), it only stores legal parentheses in stack. In this way, it uses start variable to store the legal parentheses start position. When there is a pop function and stack is empty, it will use curr_pos-start to get the length, or it will still use curr_pos and peek() for the length.

public static int getLongestParentheses(char[] chs) {
    if(chs==null||chs.length==0) {
        return 0;
    }
    int maxSize = 0;
    int start = 0;
    Stack stack = new Stack();
    for(int i=0; ilength; i++) {
        if(chs[i]=='(') {
            stack.push(i);
        }
        else if(stack.empty()) {
            start = i + 1;
        }
        else {
            stack.pop();
            maxSize = stack.isEmpty() ? Math.max(maxSize, i-start+1) : Math.max(maxSize, i-stack.peek());
        }
    }
    return maxSize;
}

public static int getMaxParentheses2(char[] chs) {
    Stack stack = new Stack();
    int max = Integer.MIN_VALUE;
    for(int i=0; ilength; i++) {
        if(stack.isEmpty() || chs[i]=='(' || chs[stack.peek()]==')') {
            stack.push(i);
        }
        else {
            stack.pop();
            int currMax = stack.isEmpty() ? i+1 : i-stack.peek();
            max = currMax > max ? currMax : max;
        }
    }
    return max;
}

Check my code on github: link
Besides, this problem also can be solved by dp. Here is from junmin’s solution: link