双指针
- 一般解决分段的问题，即求某一段的数据的值
- i为指针起点，j为指针终点
- 一种是滑动窗口，i,j一定方向相同
- 一种是夹逼，i，j相向
配合前缀和使用
a[i]+....a[j]=s[j]-s[i-1]
LeetCode
167. 两数之和 II - 输入有序数组(模板题)
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
提示：
2 <= numbers.length <= 3 * 104-1000 <= numbers[i] <= 1000numbers按 非递减顺序 排列-1000 <= target <= 1000- 仅存在一个有效答案
解题思路
1. 双指针夹逼，条件：数组升序，左右和
2. 字典，来一个存一个，如果找到target-i,获取返回
完整代码
- 双指针
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function(numbers, target) {
// 使用双指针扫描
// 1. 滑动窗口 i,j方向相同
// 2 .i，j相向
// 这里 i，j相向
// 因为数组升序，i一开始最小，j一开始最大
// i+j>target i不动，j左移 ==> target 变小 ，如果满足，直接返回，如果<target 说明i要右移 target变大
// 夹逼最后找到解
let j=numbers.length-1
for(let i=0;i<numbers.length;i++){
while(i<j&&numbers[i]+numbers[j]>target){
j--
}
if(i<j&&numbers[i]+numbers[j]===target){
return [i+1,j+1]
}
}
};
- 字典
// 可以使用字典
// 每来一个元素，计算它的另一半（target-i）
// 看是否已经存在字典中
let m=new Map()
for(let i=0;i<numbers.length;i++){
let j=target-numbers[i]
if(m.has(j)){
return [m.get(j),i+1]
}else{
m.set(numbers[i],i+1)
}
}
15. 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
解题思路
1. 三数之和，转换为两个两数之和
完整代码
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
// 解题思路
// 转换为两个两个之和
// nums[i]+nums[j]+nums[k]===0
// nums[j]+nums[k]===-nums[i]
// 先对nums进行排序，因为后面的两数之和算法需要有序
nums.sort((a,b)=>a-b)
// console.log(nums)
let res=[]
for(let i=0;i<nums.length;i++){
// start为开始下标，因为i<j<k
// 有序数组的去重 ==> nums[i] 相等时只需要计算一次
if(i>0&&nums[i]===nums[i-1]) continue
let result=twoSum(nums,i+1,-nums[i])
result.forEach(item=>{
res.push(item)
})
}
return res
};
var twoSum = function(numbers, start,target) {
// 使用双指针扫描
// 1. 滑动窗口 i,j方向相同
// 2 .i，j相向
// 这里 i，j相向
// 因为数组升序，i一开始最小，j一开始最大
// i+j>target i不动，j左移 ==> target 变小 ，如果满足，直接返回，如果<target 说明i要右移 target变大
// 夹逼最后找到解
let j=numbers.length-1
let res=[]
for(let i=start;i<numbers.length;i++){
// 这里也需要去重，即nums[j] 相同时，没有必要重复计算
if(i>start&&numbers[i]===numbers[i-1]) continue
while(i<j&&numbers[i]+numbers[j]>target){
j--
}
if(i<j&&numbers[i]+numbers[j]===target){
// 这里返回的为数组的数组，存储nums[i] 固定时，j，k的组合
// return [i+1,j+1]
res.push([-target,numbers[i],numbers[j]])
}
}
return res
};
- 注意点
- 需要对数组进行排序
- 需要去除重复项
11. 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1
提示：
n == height.length2 <= n <= 1050 <= height[i] <= 104
完整代码
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
// 解题思路
// 双指针夹逼
// 木桶水的容量由短的那块木板决定
// 刚开始 res=(j-i)*h[短]
// 如果长的木板舍弃掉，往里夹逼，容量一定减小（j-i变小，而短木板没动）
// 如果短木板舍弃，往里夹逼，（j-i变小） ，容量可能增大（短的木板下一位可能比之前的长，上限变高）
// 所以我们每次舍弃短的木板，求哪个最大
let i=0
let j=height.length-1
let max=0
while(i<j){
// 短的木板内移
if(height[i]<height[j]){
max=Math.max(max,height[i]*(j-i))
i++
}else{
max=Math.max(max,height[j]*(j-i))
j--
}
}
return max
};
84. 柱状图中最大的矩形(单调栈模板)
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4]
输出： 4
提示：
1 <= heights.length <=1050 <= heights[i] <= 104
解题思路
1.可以使用暴力枚举，但是O(n*b)
从当前矩形往左右扩散
可以相连则计算一下最值
循环全部矩形，重复上述操作
2. 单调栈解法
for 矩形
保留递增的矩形（入栈）
遇到递减的（计算递增矩形序列中的最值，pop递增矩形）
插入该递减的值
重新构成了递增的矩形序列，重复上述操作
- 计算递增矩形序列最值
完整代码
/**
* @param {number[]} heights
* @return {number}
*/
var largestRectangleArea = function(heights) {
// 单调栈解决
// 如果后面的数递增，入栈，
// 遇到递减的，我们开始计算之前单调栈的最值，pop值，直到小于新的值，新值入栈
// 再次变成了单调栈，重复上述操作
let stack=[]
// 写一个临界条件
// 最后一个值为0
// 用于终止递增的单调栈
heights.push(0)
let res=0
for(let i=0;i<heights.length;i++){
let account_width=0
// console.log(heights[i])
// 当不递增时
while(stack.length&&(stack[stack.length-1].height>=heights[i])){
// 从最高点的开始往左扩散
// width上升
account_width+=stack[stack.length-1].width
// console.log(stack)
res=Math.max(res,account_width*stack[stack.length-1].height)
stack.pop()
}
// 递增，入栈
// 这里account_width 要加上去，因为原来在栈中的被pop出去了
stack.push({width:account_width+1,height:heights[i]})
}
return res
};
239. 滑动窗口最大值(单调队列模板题)
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
完整代码
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
// 解题思路
// 维护一个单调递减的队列
// 因为后面插入的数如果大于前面的,说明前面的数是不是没用了，当前窗口的最大值为后插入的数
// 所以pop 前面的数，直到递减序列，这样可以保证队头为最大值
// 同时队头可能越界，不在窗口中，需要出队
let deQueue=[]
let res=[]
for(let i=0;i<nums.length;i++){
// 需要判断队头是否出界了
// dequeue存放的为下标，i-k为滑动串口的起点
while(deQueue.length&& deQueue[0]<=i-k) deQueue.shift()
// 存放单调递减的序列
while(deQueue.length&& nums[deQueue[deQueue.length-1]]<=nums[i]) deQueue.pop()
deQueue.push(i)
if(i>=k-1){
res.push(nums[deQueue[0]])
}
}
return res
};