每日5题Day17 - LeetCode 81 - 85

每一步向前都是向自己的梦想更近一步，坚持不懈，勇往直前！

第一题：81. 搜索旋转排序数组 II - 力扣（LeetCode）

class Solution {
    public boolean search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return false;
        }
        if (n == 1) {
            return nums[0] == target;
        }
        //由于是降序的，所以我们采用二分查找的思路
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return true;
            }
            //注意把重复的去掉
            if (nums[l] == nums[mid] && nums[mid] == nums[r]) {
                ++l;
                --r;
            } else if (nums[l] <= nums[mid]) {
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return false;
    }
}

第二题：82. 删除排序链表中的重复元素 II - 力扣（LeetCode）

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1, head);
        //注意使用三个标记位
        ListNode pre = dummy, cur = head, nex = head.next;
        while (cur != null && nex != null) {
            //如果不同，则向后移位一位
            if (cur.val != nex.val) {
                pre = pre.next;
                cur = cur.next;
                nex = nex.next;
            } else {
                //否则找到下一个不一样的
                while (nex != null && nex.val == cur.val) {
                    nex = nex.next;
                }
                //把不同的连接起来
                pre.next = nex;
                //向后移动
                cur = nex;
                if (nex != null) {
                    nex = nex.next;
                }
            }
        }
        return dummy.next;
    }
}

第三题：83. 删除排序链表中的重复元素 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        //很简单，就留一次
        if(head == null){
            return head;
        }
        ListNode dummyhead = new ListNode(-1, head);
        ListNode cur = head;
        while(cur.next != null){
            if(cur.val == cur.next.val){
                cur.next = cur.next.next;
            }
            else{
                cur = cur.next;
            }
        }
        return dummyhead.next;
    }
}

第四题：84. 柱状图中最大的矩形 - 力扣（LeetCode）

class Solution {
    public int largestRectangleArea(int[] heights) {
        int MAX = 0;
        //我们使用单调站，找出两边最低的位置
        int [] left = new int[heights.length], right = new int[heights.length];
        for (int i = 0; i < left.length; ++i) left[i] = -1; 
        for (int i = 0; i < right.length; ++i) right[i] = heights.length;     
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < heights.length; ++i) {
            while (!list.isEmpty() && heights[i] < heights[list.peekLast()]) {
                right[list.pollLast()] = i;
            }
            list.offerLast(i);
        }
        list.clear();
        for (int i = heights.length - 1; i >= 0; --i) {
            while (!list.isEmpty() && heights[i] < heights[list.peekLast()]) {
                left[list.pollLast()] = i;
            }
            list.offerLast(i);
        }
        for (int i = 0; i < heights.length; ++i) {
            //对于每一个，我们均计算最大值
            MAX = Math.max(MAX, (right[i] - left[i] - 1) * heights[i]);
        }
        return MAX;
    }
}

 第五题：85. 最大矩形 - 力扣（LeetCode）

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].length;
        int[][] left = new int[m][n];
        //我们找到以当前位置为右边界，当前行最长的1的连续长度
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }

        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '0') {
                    continue;
                }
                int width = left[i][j];
                int area = width;
                for (int k = i - 1; k >= 0; k--) {
                    width = Math.min(width, left[k][j]);
                    area = Math.max(area, (i - k + 1) * width);
                }
                ret = Math.max(ret, area);
            }
        }
        return ret;
    }
}