Day 1 | 704. Binary Search | 27. Remove Element | 35. Search Insert Position | 34. First and Last Position of Element in Sorted Array
Day 2 | 977. Squares of a Sorted Array | 209. Minimum Size Subarray Sum | 59. Spiral Matrix II
Day 3 | 203. Remove Linked List Elements | 707. Design Linked List | 206. Reverse Linked List
Day 4 | 24. Swap Nodes in Pairs| 19. Remove Nth Node From End of List| 160.Intersection of Two Lists
Day 6 | 242. Valid Anagram | 349. Intersection of Two Arrays | 202. Happy Numbe | 1. Two Sum
Day 7 | 454. 4Sum II | 383. Ransom Note | 15. 3Sum | 18. 4Sum
Day 8 | 344. Reverse String | 541. Reverse String II | 替換空格 | 151.Reverse Words in a String | 左旋轉(zhuǎn)字符串
Day 9 | 28. Find the Index of the First Occurrence in a String | 459. Repeated Substring Pattern
Day 10 | 232. Implement Queue using Stacks | 225. Implement Stack using Queue
Day 11 | 20. Valid Parentheses | 1047. Remove All Adjacent Duplicates In String | 150. Evaluate RPN
Day 13 | 239. Sliding Window Maximum | 347. Top K Frequent Elements
Day 14 | 144.Binary Tree Preorder Traversal | 94.Binary Tree Inorder Traversal| 145.Binary Tree Postorder Traversal
Day 15 | 102. Binary Tree Level Order Traversal | 226. Invert Binary Tree | 101. Symmetric Tree
Day 16 | 104.MaximumDepth of BinaryTree| 111.MinimumDepth of BinaryTree| 222.CountComplete TreeNodes
Day 17 | 110. Balanced Binary Tree | 257. Binary Tree Paths | 404. Sum of Left Leaves
Day 18 | 513. Find Bottom Left Tree Value | 112. Path Sum | 105&106. Construct Binary Tree
Day 20 | 654. Maximum Binary Tree | 617. Merge Two Binary Trees | 700.Search in a Binary Search Tree
Day 21 | 530. Minimum Absolute Difference in BST | 501. Find Mode in Binary Search Tree | 236. Lowes
Day 22 | 235. Lowest Common Ancestor of a BST | 701. Insert into a BST | 450. Delete Node in a BST
Day 23 | 669. Trim a BST | 108. Convert Sorted Array to BST | 538. Convert BST to Greater Tree
Day 24 | 77. Combinations
Day 25 | 216. Combination Sum III | 17. Letter Combinations of a Phone Number
Day 27 | 39. Combination Sum | 40. Combination Sum II | 131. Palindrome Partitioning
Day 28 | 93. Restore IP Addresses | 78. Subsets | 90. Subsets II
Day 29 | 491. Non-decreasing Subsequences | 46. Permutations | 47. Permutations II
Day 30 | 332. Reconstruct Itinerary | 51. N-Queens | 37. Sudoku Solver
Day 31 | 455. Assign Cookies | 376. Wiggle Subsequence | 53. Maximum Subarray
Day 32 | 122. Best Time to Buy and Sell Stock II | 55. Jump Game | 45. Jump Game II
Day 34 | 1005. Maximize Sum Of Array After K Negations | 134. Gas Station | 135. Candy
Day 35 | 860. Lemonade Change | 406. Queue Reconstruction by Height | 452. Minimum Number of Arrows
Day 36 | 435. Non-overlapping Intervals | 763. Partition Labels | 56. Merge Intervals
Day 37 | 738. Monotone Increasing Digits | 714. Best Time to Buy and Sell Stock | 968. BT Camera
Day 38 | 509. Fibonacci Number | 70. Climbing Stairs | 746. Min Cost Climbing Stairs
Day 39 | 62. Unique Paths | 63. Unique Paths II
Day 41 | 343. Integer Break | 96. Unique Binary Search Trees
Day 42 | 0-1 Backpack Basic Theory（一）| 0-1 Backpack Basic Theory（二）| 416. Partition Equal Subset Sum
Day 43 | 1049. Last Stone Weight II | 494. Target Sum | 474. Ones and Zeroes
Day 44 | Full Backpack Basic Theory | 518. Coin Change II | 377. Combination Sum IV
Day 45 | 70. Climbing Stairs | 322. Coin Change | 279. Perfect Squares
Day 46 | 139. Word Break | Backpack Question Summary
Day 48 | 198. House Robber | 213. House Robber II | 337. House Robber III
Day 49 | 121. Best Time to Buy and Sell Stock I | 122. Best Time to Buy and Sell Stock II
Day 50 | 123. Best Time to Buy and Sell Stock III | 188. Best Time to Buy and Sell Stock IV
Day 51 | 309. Best Time to Buy and Sell Stock with Cooldown | 714. with Transaction Fee
Day 52 | 300. Longest Increasing Subsequence | 674. Longest Continuous Increasing Subsequence | 718. Maximum Length of Repeated Subarray
Day 53 | 1143. Longest Common Subsequence | 1035. Uncrossed Lines | 53. Maximum Subarray
Day 55 | 392. Is Subsequence | 115. Distinct Subsequences
Day 56 | 583. Delete Operation for Two Strings | 72. Edit Distance
Day 57 | 647. Palindromic Substrings | 516. Longest Palindromic Subsequence
Day 58 | 739. Daily Temperatures | 496. Next Greater Element I
Day 59 | 503. Next Greater Element II | 42. Trapping Rain Water

84. Largest Rectangle in Histogram

Question Link文章來源地址http://www.zghlxwxcb.cn/news/detail-652514.html

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(0);

        int[] newHeights = new int[heights.length + 2];
        System.arraycopy(heights, 0, newHeights, 1, heights.length);

        int result = 0;
        for(int i = 1; i < newHeights.length; i++){
            if(newHeights[i] > newHeights[stack.peek()]){
                stack.push(i);
            }else if(newHeights[i] == newHeights[stack.peek()]){
                stack.pop();
                stack.push(i);
            }else{
                while(newHeights[i] < newHeights[stack.peek()]){
                    int mid = stack.pop();
                    int left = stack.peek();
                    int right = i;
                    int w = right - left - 1;
                    int h = newHeights[mid];
                    result = Math.max(w * h, result);
                }
                stack.push(i);
            }
        }
        return result;
    }
}

• Compare to 739. Daily Temperatures and 42. Trapping Rain Water are finding the first bar that larger than the current bar. This question is to find the first bar smaller than the current one. So the order of the elements in the monotonic stack is from largest to smallest.
• We must add the 0 at the beginning of the heights array. Cause if the array itself is in descending order like [8,6,4,2], after 8 is in the stack, 6 is compared to the 8. We could get the mid(8), right(6), but won’t be able to get the left bar. Cause after popping out the 8, there is no element in the stack.
• We must add the 0 at the end of the heights array. Cause if the array itself is in ascending order like [2,4,6,8] order, all the elements in the stack will be descending and won’t be able to trigger the case 3.

到了這里，關(guān)于Day 60 | 84. Largest Rectangle in Histogram的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！