215.找第k大元素

三路的快速排序

快速选择

法2.堆选

（堆排序）

11.盛更多水的容器

代码1

代码2

560.和为K的子数组（题意！）

惯性思维

正解

21.合并生序链表

递归写法

128.最长连续序列

20.有效的括号

面试的时候不好好审题，太急，直接惯性思维用三个栈了

121.买卖股票的最佳时机

215.找第k大元素

那么这道题想要时间复杂度低，肯定是不能全部排序的

先来讲讲

三路的快速排序

三路快排在两路的基础上加上了=的部分，

为了处理全部元素相同的特殊情况

总的来说就是通过三个指针维护左边<、中间=、右边>

如下图的左上角所示

JS代码如下

function quickSort3Way(arr, left = 0, right = arr.length - 1) {if (left >= right) return;let lt = left;         // 小于区域的右边界let gt = right;        // 大于区域的左边界let pivot = arr[left]; // 选取第一个元素为基准let i = left + 1;      // lt 至 gt 中、=pivot右边、的当前正在判断的位置while (i <= gt) {if (arr[i] < pivot) {[arr[lt], arr[i]] = [arr[i], arr[lt]];lt++;i++;//原本lt位置是=pivot的，所以<分支中可以直接i++判断下一个} else if (arr[i] > pivot) {[arr[i], arr[gt]] = [arr[gt], arr[i]];gt--;} else {i++;//而gt位置是未知的，不能i++}}quickSort3Way(arr, left, lt - 1);quickSort3Way(arr, gt + 1, right);
}let nums = [3, 5, 2, 3, 1, 3, 4, 2, 3];
quickSort3Way(nums);
console.log(nums);

注意：

//原本lt位置是=pivot的，所以<分支中可以直接i++判断下一个

//而gt位置是未知的，不能i++

快速选择

快速选择就是在快速排序的基础上，对于最后的部分进行判断分支剪枝，从而只进行必要的排序

if (k_smallset<ls){return quickSelect(arr,left,lt-1,k_smallest);
}else if{return quickSelect(arr,gt+1,right,k_smallest);
}else{return arr[lf];
}

法2.堆选

JS中没有内置堆模块，python自带了，而且还有两个（heapq、PriorityQueue）

通过最小堆找第k大（用最大堆的话得维护所有元素且弹k次）

将数组压入堆，维护至最大的k个元素（有多于k个：弹出最小的也就是弹出堆顶），那么堆顶就是第k大

import heapqdef findKthLargest(nums, k):heap = []for num in nums:heapq.heappush(heap, num)if len(heap) > k:heapq.heappop(heap)return heap[0]

（堆排序）

堆排序就是一直 heappop

import heapqdef heap_sort(nums):heapq.heapify(nums)  # O(n) 建堆res = [heapq.heappop(nums) for _ in range(len(nums))]return res

11.盛更多水的容器

var maxArea = function(height) {let ans=0;for(let l=0;l<height.length-1;l++){let r=height.length-1;let hnow=0;while(r>l){if (height[r]>hnow){ans=Math.max(ans,(r-l)*Math.min(height[l],height[r]));hnow=height[r];}r--;//方向会影响}}return ans;
};

上面我的第一次贪心效果并不是很好

实际上：由于双指针往中间时 d小了，只有 h大才可能S大

只需要在 h 更大的时候才需要更新 ans

具体细节：短板效应-那边更小动那边

代码1

var maxArea = function(height) {let ans = 0, left = 0, right = height.length - 1;while (left < right) {const area = (right - left) * Math.min(height[left], height[right]);ans = Math.max(ans, area);if (height[left] < height[right]) {left++;} else {right--;}}return ans;
};

代码2

var maxArea=function(height){let l=0;let r=height.length-1;let lh=height[l];let rh=height[r];let ans=(r-l)*Math.min(lh,rh);while(l<r){if (lh<rh){l++;lnow=height[l];if(lnow>lh){lh=lnow;ans=Math.max(ans,(r-l)*Math.min(lh,rh));}}else{r--;rnow=height[r];if(rnow>rh){rh=rnow;ans=Math.max(ans,(r-l)*Math.min(lh,rh));}}}return ans;
}

看上去代码能节省更新 ans 的次数，但是实际上代码1更快

简洁的代码更强健

560.和为K的子数组（题意！）

不急
上来就写了一发DFS，但是题意是连续子数组

惯性思维

var subarraySum = function(nums, k) {let ans = [];function dfs(step, sum, choice) {if (sum === k) {ans.push([...choice]);  // 通过展开运算符，拷贝，避免后续更改}if (step === nums.length) {return;}choice.push(nums[step]);dfs(step + 1, sum + nums[step], choice);choice.pop();  // 直接pop，恢复现场dfs(step + 1, sum, choice);}dfs(0, 0, []);return ans;
};

正解

连续：前缀和

通过哈希表优化：找目标

var subarraySum = function(nums, k) {let count = 0;let sum = 0;let map = new Map();map.set(0, 1);  // 前缀和为0出现1次for (let num of nums) {sum += num;if (map.has(sum - k)) {count += map.get(sum - k);}map.set(sum, (map.get(sum) || 0) + 1);}return count;
};

(map.get(sum) || 0) 通过或语句将未出现时的 undifined 转为 0

21.合并生序链表

一看就是双指针

注意力扣的链表类

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }

当最后一方没有时，返回另一方，直接接在答案后面即可

递归写法

var mergeTwoLists = function(l1, l2) {if (l1 === null) {return l2;} else if (l2 === null) {return l1;} else if (l1.val < l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;} else {l2.next = mergeTwoLists(l1, l2.next);return l2;}
};

复杂度比下面的迭代要好

var mergeTwoLists = function(l1, l2) {const prehead = new ListNode(-1);let prev = prehead;while (l1 != null && l2 != null) {if (l1.val <= l2.val) {prev.next = l1;l1 = l1.next;} else {prev.next = l2;l2 = l2.next;}prev = prev.next;}prev.next = l1 === null ? l2 : l1;return prehead.next;
};

128.最长连续序列

Set去重后

通过哈希表判断连续

var longestConsecutive=function(nums){const st=new Set(nums);let ans=0;for(const x of st){//注意下面用的都是stif(st.has(x-1)){continue;//上一个一定已经判断过了}let y=x+1;while(st.has(y)){y++;}ans=Math.max(ans,y-x);}return ans;
}

20.有效的括号

面试的时候不好好审题，太急，直接惯性思维用三个栈了

但是这怎么能三个栈呢，题目里面说了是正确的闭合，也就是 [ ( ] ) 是错的

直接开一个就够了

然后用哈希表优化逻辑

var isValid = function(s) {if (s.length % 2) { // s 长度必须是偶数return false;}const mp = {'(': ')', '[': ']', '{': '}'};const st = [];for (const c of s) {if (mp[c]) { // c 是左括号st.push(mp[c]); // 入栈} else if (st.length === 0 || st.pop() !== c) { // c 是右括号return false; // 没有左括号，或者左括号类型不对}}return st.length === 0; // 所有左括号必须匹配完毕
};

121.买卖股票的最佳时机

维护之前最小值这一变量

var maxProfit = function(prices) {let ans=0;let min=prices[0];for(let i=1;i<prices.length;i++){let d=prices[i]-min;ans=Math.max(ans,d);if(prices[i]<min){min=prices[i];}}return ans;
};