373. Find K Pairs with Smallest Sums
題目網址：https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/
題意：給兩個升序排列的 array nums1 和 nums2。
定義 pair (u, v), 其中 u 來自 nums1, v 來自 nums2
求和最小的 k 個 pair
Solution 1：
想法：利用 Heap, 解法同 378. Kth Smallest Element in a Sorted Matrix, pair 分別存 nums1 第 i 個元素、nums2 第 j 個元素 (只存 index, 不存 val), 然後用 minHeap 取最小的 sum(nums1[i], nums2[j])
class Solution {public: vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) { // 重要: ...
452. Minimum Number of Arrows to Burst Balloons
題目網址：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/
題意：有一些氣球貼在 XY 平面上, 給一 array points, 其中 points[i] = [x_start, x_end] 代表氣球水平直徑在 x_start 和 x_end 的氣球。
一支弓箭可沿著 x 軸完全垂直地射出。在座標 x 射出弓箭, 若有一個氣球的直徑滿足 x_start **≤** x **≤** x_end, 則該氣球會被引爆。弓箭被射出後, 可以無限地前進。
返回引爆所有氣球的最小弓箭數。
Solution 1：
想法：利用 Greedy, 每增加一支箭, 想辦法讓那支箭盡可能地引爆多一點的氣球。每一支箭的射出位置為「所有氣球中右邊界位置最靠左的」可以引爆最多氣球。如果某個氣球的起始點大於 end, 說明前面的箭無法覆蓋到當前的氣球, 那麼就得再來一支箭
e.g. points = [[1, 10], [2, 7], [8, 11]]+
當只有 [[1, 10], [2, 7]] 時, 此時弓 ...
852. Peak Index in a Mountain Array
題目網址：https://leetcode.cn/problems/peak-index-in-a-mountain-array/
題意：如果以下屬性成立，我們就稱 arr 為山。
arr.length >= 3
arr[0] < arr[1] < ... arr[i-1] < arr[i]
arr[i] > arr[i+1] > ... > arr[arr.length - 1]
找到 arr 的山峰 idx = i, 滿足arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Solution：
想法：利用 Binary Search, 不斷找中點, 並和後面一數比較, 判斷要往左邊還右邊來縮小範圍
class Solution {public: int peakIndexInMountainArray(vector<int>& arr) { ...
162. Find Peak Element
題目網址：https://leetcode.cn/problems/find-peak-element/
題意：給一整數 array nums, 找到峰值並返回其 index。nums 中可能有多個峰值, 返回任何一個峰值的 index 即可。
假設 nums[-1] = nums[n] = -∞
設計 $O(log(n))$ time 的演算法。
Solution：
想法：利用 Binary Search, 從一個位置開始, 不斷地向高處走, 那麼最終一定可以到達一個峰值位置, 根據比較 nums[i − 1], nums[i], nums[i + 1] 三個位置的值來縮小左邊界 or 右邊界, 有以下幾種情況：
nums[i − 1] < nums[i] > nums[i + 1] : i 即為峰值
nums[i − 1] < nums[i] < nums[i + 1] : i 處於上坡, 峰值在右半邊, 故縮小左邊界
nums[i − 1] > nums[i] > nums[i + 1] : i 處於下坡, 峰值在左半邊, 故縮小右邊界 ...
81. Search in Rotated Sorted Array II
題目網址：https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/
題意：存在一整數 array nums, 按非降序排列, nums 中的數值有可能會重複。
給一旋轉後的 nums 和一整數 target, 如果 nums 中存在 target, 則返回其 true; 否則, 返回 false。
盡可能地減少操作步驟。
Solution：
想法：類似 33. Search in Rotated Sorted Array, 差別在本題的 nums 可能會有重複數, 導致 nums[left] == nums[mid] 時, 無法判斷 [left, mid] 和 [mid + 1, right] 哪個才是有序的
e.g. nums = [1,1,1,0,1], target = 0無法判斷 [0,2] 和 [3,4] 哪個才是有序的。
對於這種情況, 將 left + 1, 然後在新區間繼續做 Binary Search
class Solution {public: bool search(v ...