154 寻找旋转排序数组中的最小值 II
二分本质上是二段性，而有重复元素的情况下，二段性就被破坏了，要恢复二段性；
因此，可以去掉，头和尾中【相同】的元素，来达到去除不满足的情况；
class Solution {
? ? public int findMin(int[] nums) {
? ? ? ? int n = nums.length;
? ? ? ? int l = 0, r = n - 1;
? ? ? ? while (l < r && nums[0] == nums[r]) r--;? // 恢复二段性
? ? ? ? while (l < r) {
? ? ? ? ? ? int mid = l + r + 1 >> 1;
? ? ? ? ? ? if (nums[mid] >= nums[0]) {
? ? ? ? ? ? ? ? l = mid;//? 这样写保证了找到的是最右边的数
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? r = mid - 1;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return r + 1 < n ? nums[r + 1] : nums[0];?
? ? ? ? // 如果r+1 > n ，说明没找到，原数组就是自然排列的，因此，第一个数就是最小的
? ? }
}
1438 绝对差不超过限制的最长连续子数组
双指针
public int longestSubarray(int[] nums, int limit) {
int n =nums.length;
int ans = 0;
Deque<Integer> max = new ArrayDeque<>(),min = new ArrayDeque<>();
// 创建max，min对应的队列，队列的头部是最值
//注意队列存的是下标而不是具体元素的值，
//这样才方便在滑动的时候判断一个元素是否已经不属于左右区间内了
for(int r=0,l=0;r<n;r++) {
//如果当前元素的值大于max队列尾的值，那么就将队列中所有小于当前元素的值弹出，
//再将当前元素的【下标】入队列
while(!max.isEmpty()&&nums[r]>=nums[max.peekLast()]) max.pollLast();
while(!min.isEmpty()&&nums[r]<=nums[min.peekLast()]) min.pollLast();
max.addLast(r);
min.addLast(r);
// 队列头部存的是两个队列的最值，取出并进行判断
while(Math.abs(nums[max.peekFirst()]-nums[min.peekFirst()])>limit) {
l++;
// 如果取出的元素已经小于左边界了，那么弹出；
if(max.peekFirst() < l) max.pollFirst();
if(min.peekFirst() < l) min.pollFirst();
}
ans = Math.max(ans, r-l+1);
}
return ans;
}滑动窗口+双指针
三叶题解分析：https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/solution/xiang-jie-er-fen-hua-dong-chuang-kou-dan-41g1/
public int longestSubarray(int[] nums, int limit) {
int n =nums.length;
int l =1 ,r = n;
while(l<r) {
int mid = l + r + 1 >> 1 ;
// 通过二分来找到满足mid长度的情况
if(check(nums,mid,limit)) {
l = mid;
}else {
r = mid-1;
}
}
return r ;
}
boolean check (int[] nums,int len,int limit) {
int n = nums.length;
Deque<Integer> max = new ArrayDeque<>(),min = new ArrayDeque<>();
for(int r=0,l=r-len+1;r<n;r++,l=r-len+1) {
//每次通过r来确定左端点，因为长度是固定的
//当队列头的值小于左端点l的时候，弹出
if(!max.isEmpty()&&max.peekFirst()<l) max.pollFirst();
//当前值比队列尾大时，弹出，直到找到一个比当前值大或是队列空了
while(!max.isEmpty()&&nums[r] >= nums[max.peekLast()]) max.pollLast();
max.addLast(r);
if(!min.isEmpty()&&min.peekFirst()<l) min.pollFirst();
while(!min.isEmpty()&&nums[r]<= nums[min.peekLast()]) min.pollLast();
min.addLast(r);
if(l>=0&&Math.abs(nums[max.peekFirst()]-nums[min.peekFirst()])<=limit)
return true; //找到有一组满足情况时，当前mid便是满足条件的
}
//当找完所有的情况，没有为true时，就返回false
return false ;
}二叉树对称问题
二叉树的镜像
https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof/
不能在原来节点的基础上直接进行交换，要重新建立新的节点；而建立新的节点，不能前序进行建立，因为前序并不知道之后节点的情况，而翻转的创建的时候，应要包含子树；否则，子树并没有跟着根节点一起翻转；
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = mirrorTree(root.left);
TreeNode right = mirrorTree(root.right);
root.left = right;
root.right = left;
return root;
}对称的二叉树
题解
?
class Solution {
public boolean isSymmetric(TreeNode root) {
return root == null ? true : recur(root.left, root.right);
}
boolean recur(TreeNode L, TreeNode R) {
if(L == null && R == null) return true;
if(L == null || R == null || L.val != R.val) return false;
return recur(L.left, R.right) && recur(L.right, R.left);
}
}?
