LeetCode 81-85

81. Search in Rotated Sorted Array II

分析：

此题和第33题的区别就是，这道题数组中的元素可能由重复的。
只需加上以下几行代码，就又可以保证mid左右某侧都是递增的了。

             if (nums[lo] == nums[mid]) {
                lo++;
                continue;
            }

Java:

class Solution {
    public boolean search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[lo] == nums[mid]) {
                lo++;
                continue;
            }
            //此时mid左侧的都是递增的
            if (nums[lo] < nums[mid]) {
                if (nums[mid] > target && nums[lo] <= target) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else { //此时mid右侧都是递增的
                if (nums[mid] < target && nums[hi] >= target) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return false;
    }
}

82. Remove Duplicates from Sorted List II

分析：

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。
先创建一个虚拟头结点，cur指向虚拟头结点，当cur.next和cur.next.next都不为空时，一直循环。
只要cur.next.val = cur.next.next.val 说明有重复值，这个时候再用一个新结点temp指向cur.next，即重复值的第一个元素，然后不断循环找到重复值的最后一个元素，再把 cur.next = temp.next 即完成了重复值的删去。

Java：

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                ListNode temp = cur.next;
                while (temp != null && temp.next != null && temp.val == temp.next.val) {
                    temp = temp.next;
                }
                cur.next = temp.next;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

83. Remove Duplicates from Sorted List

分析：

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
不断遍历，只要下一个结点的值等于当前结点，就把当前结点指向下下个结点。

Java:

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.next != null) {
                ListNode next = cur.next;
                if (cur.val == next.val) {
                    cur.next = next.next;
                } else {
                    cur = cur.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
}

84. Largest Rectangle in Histogram

分析：

方法一：暴力枚举
枚举所有的柱子，将它们的高设定为矩形的高。
然后只需从某个柱子出发往两侧找第一个比它矮的柱子，那么就是矩形的边界。
遍历一遍之后就可以把矩形最大值求出来。
方法二：单调栈
使用单调栈快速确定每一根柱子的左右边界。

单调递增栈的特性：
栈内元素保持单调递增，进栈时，如果新的元素比栈顶元素大，则直接进栈。如果新的元素比栈顶元素小，则不断出栈，直至栈顶元素比新的元素小，然后再进栈。
当某个元素出栈时，新栈顶的元素一定是前一个比它小的元素，待入栈的元素一定是后一个比它小的元素。

在数组左右插入一根高为0的柱子，使代码更简洁，不用考虑出栈的时候栈为空的情况，也不用考虑遍历完成之后，栈中还有元素的情况。

时间复杂度On,空间复杂度On######Java：

class Solution {
    public int largestRectangleArea(int[] heights) {
        int res = 0;
        for (int i = 0; i < heights.length; i++) {
            int height = heights[i];
            int left = i, right = i;
            while (left >= 0 && heights[left] >= height) {
                left--;
            }
            while (right <= heights.length - 1 && heights[right] >= height) {
                right++;
            }
            res = Math.max(res, height * (right - left - 1));
        }
        return res;
    }
}

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] newHeights = new int[heights.length + 2];
        int len = heights.length + 2;
        newHeights[0] = newHeights[len - 1] = 0;
        //src源数组,srcPos复制开始位置,dest目标数组,destPos目标数组开始位置,length复制的长度
        System.arraycopy(heights, 0, newHeights, 1, heights.length);
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        int res = 0;
        for (int i = 1; i < len; i++) {
            while (newHeights[stack.peek()] > newHeights[i]) {
                int curHeight = newHeights[stack.poll()];
                int width = i - stack.peek() - 1;
                res = Math.max(res, curHeight * width);
            }
            stack.push(i);
        }
        return res;
    }
}

85. Maximal Rectangle

分析：

可以转化为84题，只需要求出每一层的 heights[] 然后传给上一题的函数。

Java：

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int[] heights = new int[matrix[0].length];
        int maxArea = 0;
        for (int row = 0; row < matrix.length; row++) {
            //遍历每一列，更新高度
            for (int col = 0; col < matrix[0].length; col++) {
                if (matrix[row][col] == '1') {
                    heights[col] += 1;
                } else {
                    heights[col] = 0;
                }
            }
            //调用上一题的解法，更新函数
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }
    
    public int largestRectangleArea(int[] heights) {
        int[] newHeights = new int[heights.length + 2];
        int len = heights.length + 2;
        newHeights[0] = newHeights[len - 1] = 0;
        //src源数组,srcPos复制开始位置,dest目标数组,destPos目标数组开始位置,length复制的长度
        System.arraycopy(heights, 0, newHeights, 1, heights.length);
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        int res = 0;
        for (int i = 1; i < len; i++) {
            while (newHeights[stack.peek()] > newHeights[i]) {
                int curHeight = newHeights[stack.poll()];
                int width = i - stack.peek() - 1;
                res = Math.max(res, curHeight * width);
            }
            stack.push(i);
        }
        return res;
    }
}