每日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;}
}