目錄

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