Stack

Represent the computation in stack style.

388. Longest Absolute File Path

Calculation of the current path just needs the length of the parent path (dir/subdir2) + length of current part of the path (/subsubdir2). Other information is discarded as required computations are done. Problem structure:

 dir 
    subdir1
        file1.ext
        subsubdir1
    subdir2
        subsubdir2
            file2.ext

Use the stack to store the index, not necessarily storing the value.

//use stack to store the index of the array, we can still using the array to do val compare
//some problem relies on this skill
for(int i=0; i<n; i++) {
    while(!s.isEmpty() && temperatures[i] > temperatures[s.peek()]) {
        int index = s.pop();
        result[index] = i - index;
    }
    s.push(i);   
}

Use the stack to store the index, it will allow us to compute extra information required e.g. width.

84. Largest Rectangle in Histogram

The stack itself is to maintain a stream of data which is useful for our computation of the problem. To store the element push order in index instead of value could give us more information e.g. width of something. Watch out for several minor things:

• what triggers the stack pop() and computation, how should you handle when it reaches the end of the data stream/array
• i pointer increment: when we comparing / pop, no need to increase index i
• how to use the stored index to compute extra information, special case? e.g. when you pop the last element of the stack

class Solution {
    public int largestRectangleArea(int[] heights) {
        if(heights==null || heights.length<1) return 0;
        int maxArea = 0;

        Stack<Integer> rectIndexStack = new Stack<>();

        int i=0;
        while(i<=heights.length) {
            int h = i==heights.length? 0: heights[i]; //trigger the stack pop/computation at the end of data
            if(rectIndexStack.isEmpty() || h >= heights[rectIndexStack.peek()])
                rectIndexStack.push(i++);
            else {
                int top = rectIndexStack.pop();
                int width = rectIndexStack.isEmpty()? i: i-top;
                maxArea = Math.max(heights[top]*width, maxArea);
            }
        }

        return maxArea;
    }
}

456. 132 Pattern

Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k 
and ai < ak < aj. Design an algorithm that takes a list of n numbers as input 
and checks whether there is a 132 pattern in the list.

Note: n will be less than 15,000.

Example 1:
Input: [1, 2, 3, 4]

Output: False

// assume arrage s1, s3, s2 (i, j, k) s1<s2<s3
// s1 need to smaller than s2

//when num[i] as S3, we can see what's the max value of s2 which is smaller than it.
//think like a mountain... all the s2Candidate find will be larger and larger... 
//otherwise we will already get the answer
//
//          /\
//        \/  \
//             \