84. Largest Rectangle in Histogram

class Solution {
    public int largestRectangleArea(int[] heights) {
        int area = 0;
        int m = 0; 
        for (int i = 0; i < heights.length; i++) {
            int j = i + 1;
            area = heights[i]; 
            while (j < heights.length && heights[i] <= heights[j]) {
                area += heights[i];
                j++; 
            }
            j = i - 1;
            
            while (j >= 0 && heights[i] <= heights[j]) {
                area += heights[i];
                j--;
            }
            
            m = (m > area) ? m : area;
        }
        
        return m; 
    }
}

93 / 96 test cases passed.
Time limit exceeded.

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        int length = heights.length;
        for (int i = 0; i < length; i++) {
            int minHeight = Integer.MAX_VALUE;
            for (int j = i; j < length; j++) {
                minHeight = Math.min(minHeight, heights[j]);
                maxArea = Math.max(maxArea, minHeight * (j - i + 1));
            }
        }
        return maxArea;
    }
}

91 / 96 test cases passed.
Time Limit Exceeded

이게 조금 더 빠를줄 알았는데 아니네요..

public class Solution {
    public int calculateArea(int[] heights, int start, int end) {
        if (start > end)
            return 0;
        int minindex = start;
        for (int i = start; i <= end; i++)
            if (heights[minindex] > heights[i])
                minindex = i;
        return Math.max(heights[minindex] * (end - start + 1),
                        Math.max(calculateArea(heights, start, minindex - 1),
                                calculateArea(heights, minindex + 1, end))
                );
    }

    public int largestRectangleArea(int[] heights) {
        return calculateArea(heights, 0, heights.length - 1);
    }
}

Divide & Conquer 방식...근데 이것도 타임리밋이네요 미치겠다 별들아 ㅎ

95 / 96 test cases passed.
Time Limit Exceeded

public class Solution {
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        int length = heights.length;
        int maxArea = 0;
        for (int i = 0; i < length; i++) {
            while ((stack.peek() != -1)
                    && (heights[stack.peek()] >= heights[i])) {
                int currentHeight = heights[stack.pop()];
                int currentWidth = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, currentHeight * currentWidth);
            }
            stack.push(i);
        }
        while (stack.peek() != -1) {
            int currentHeight = heights[stack.pop()];
            int currentWidth = length - stack.peek() - 1;
            maxArea = Math.max(maxArea, currentHeight * currentWidth);
        }
        return maxArea;
    }
}

Stack을 이용한 방식

Runtime: 16 ms, faster than 50.80% of Java online submissions for Largest Rectangle in Histogram.
Memory Usage: 52.2 MB, less than 16.35% of Java online submissions for Largest Rectangle in Histogram.