下一个排列
leetcode 大意就是
- 例如，
arr = [1,2,3]的下一个排列是[1,3,2]。 - 类似地，
arr = [2,3,1]的下一个排列是[3,1,2]。 - 而
arr = [3,2,1]的下一个排列是[1,2,3]，因为[3,2,1]不存在一个字典序更大的排列。
必须 原地 修改，只允许使用额外常数空间。
js
输入：nums = [1,2,3]
输出：[1,3,2]
输入：nums = [3,2,1]
输出：[1,2,3]
输入：nums = [1,1,5]
输出：[1,5,1]
思路
- 如何变大：从低位挑一个大一点的数，交换前面一个小一点的数。
- 变大的幅度要尽量小。
像 [3,2,1] 这样递减的，没有下一个排列，已经稳定了，没法变大。
像 [1,5,2,4,3,2] 这种，怎么稍微变大？
- 从右往左，寻找第一个比右邻居小的数，把它换到后面去
- “第一个”意味着尽量是低位，“比右邻居小”意味着它是从右往左的第一个波谷
- 比如，1 5 (2) 4 3 2，中间这个 2。
- 接着还是从右往左，寻找第一个比这个 2 大的数。15 (2) 4 (3) 2，交换后：15 (3) 4 (2) 2。
- 还没结束！变大的幅度可以再小一点，仟位微变大了，后三位可以再小一点。
- 后三位肯定是递减的，翻转，变成[1,5,3,2,2,4]，即为所求。
代码
js
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
function nextPermutation(nums) {
let i = nums.length - 2; // 向左遍历，i从倒数第二开始是为了nums[i+1]要存在
while (i >= 0 && nums[i] >= nums[i + 1]) i--; // 寻找第一个小于右邻居的数
// 当前的 i 是存在的 从它身后挑一个数，和它换
if (i >= 0) {
let j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) j--; // 寻找第一个大于 nums[i] 的数
[nums[i], nums[j]] = [nums[j], nums[i]]; // 两数交换，实现变大
}
// 如果 i = -1，说明是递减排列，如 3 2 1，没有下一排列，直接翻转为最小排列：1 2 3
let l = i + 1;
let r = nums.length - 1;
while (l < r) {
// i 右边的数进行翻转，使得变大的幅度小一些
[nums[l], nums[r]] = [nums[r], nums[l]];
l++;
r--;
}
}
三数之和
力扣题目链接: 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
js
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
思路
- 做排序，如果 i > 0 后面也没有要遍历下去的必要
- 当前 i，定义指针
l = i + 1, r = len - 1, 当 l < r 情况下，计算 sum 值- sum > 0, r--
- sum < 0, l++
- sum === 0
- 因为要求不含重复的三元组，这里再次对相同的元素值进行过滤
- l++ && r--
代码
js
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
nums.sort((a, b) => a - b); // 排序
let len = nums.length;
let result = [];
for (let i = 0; i < len; i++) {
// 如果当前数字大于0，则三数之和一定大于0，所以结束循环
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
let [l, r] = [i + 1, len - 1];
while (l < r) {
let sum = nums[i] + nums[l] + nums[r];
if (sum > 0) r--;
else if (sum < 0) l++;
else {
// sum
result.push([nums[i], nums[l], nums[r]]);
while (l < r && nums[l] === nums[l + 1]) l++; // 去重
while (l < r && nums[r] === nums[r - 1]) r--; // 去重
l++;
r--;
}
}
}
return result;
};
接雨水
js
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）
思路
我们先明确几个变量的含义
js
leftMax: 左边的最大值，它是从左往右遍历找到的
rightMax: 右边的最大值，它是从右往左遍历找到的
left: 从左往右处理的当前下标
right: 从右往左处理的当前下标
在某个位置 i 处,它能存的水，取决于它左右两边的最大值中较小的一个，这点很好理解，和木桶原理类似，取决于短板。
如图，当 i = 4，他能存储的水量取决于左右两根柱子的最小高度
代码
js
/**
* @param {number[]} height
* @return {number}
*/
var trap = function (height) {
let sum = 0;
let [left, right, leftMax, rightMax] = [0, height.length - 1, 0, 0];
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
// 以左边为准
if (leftMax <= rightMax) {
sum += leftMax - height[left];
left++;
} else {
sum += rightMax - height[right];
right--;
}
}
return sum;
};