LeetCode : 84. Largest Rectangle in Histogram

// Runtime: 148 ms
// Memory Usage: 93.1 MB
// Ref : https://leetcode.com/submissions/detail/657229072
class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Node> st = new Stack<>();

        int ans = -1;

        if (heights.length < 1) {
            return heights[0];
        }

        st.push(new Node(0, heights[0]));

        for (int i = 1; i < heights.length; i++) {
            int pos = i;
            while (!st.isEmpty() && st.peek().val > heights[i]) {
                Node node = st.pop();
                pos = node.pos;
                ans = Math.max(ans, (i - node.pos) * node.val);
            }
            st.push(new Node(pos, heights[i]));
        }

        Node rightNode = new Node(heights.length, st.peek().val);

        while (!st.isEmpty()) {
            Node node = st.pop();
            ans = Math.max(ans, (rightNode.pos - node.pos) * node.val);
        }
        return ans;
    }

    private class Node {
        public int pos;
        public int val;

        public Node(int pos, int val) {
            this.pos = pos;
            this.val = val;
        }
    }
}

// Runtime: 75 ms
// Memory Usage: 88.8 MB
// Ref : https://leetcode.com/submissions/detail/621037929
class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        Stack<Integer> s = new Stack<>();
        int maxArea = 0;
        for (int i = 0; i <= len; i++) {
            int h = (i == len ? 0 : heights[i]);
            if (s.isEmpty() || h >= heights[s.peek()]) {
                s.push(i);
            } else {
                int tp = s.pop();
                maxArea = Math.max(maxArea, heights[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
                i--;
            }
        }
        return maxArea;
    }
}