42. Trapping Rain Water
題目網址：https://leetcode.cn/problems/trapping-rain-water/
題意：給 n 個非負整數, 代表每個寬度為 1 的柱子之高度圖, 計算按此排列的柱子, 在下雨後能接多少雨水。
Solution 1：（TLE 無法通過）
想法：利用暴力法, 我們計算每個 col 所能接住的水量, 因此對於每個 i 我們要在 height[0 ~ i] 和 height[i ~ (n - 1)] 中分別找出最大值 leftMax 和 rightMax, 則該 col 所能接住的水量 = min(leftMax, rightMax) - height[i]
class Solution {public: int trap(vector<int>& height) { int res = 0, n = height.size(); for (int i = 0; i < n; ++i) { auto it = height.begin ...
739. Daily Temperatures
題目網址: https://leetcode.cn/problems/daily-temperatures/
題意: 給一整數 array temperatures 代表每天的溫度。請返回 array res, 其中 res[i] 是指對於第 i 天, 下一個更高溫度是出現在幾天後。如果氣溫在這之後都不會升高, 則該位置用 0 來代替。
Solution：
想法：利用 Stack, 使用 Monotonic（遞減） Stack stk 紀錄 {temperature, idx}, 一旦當前溫度 temperatures[i] 比 stk.top().first 還高, 則不斷將 stk.top() 取出, 並計算 res[idx], 直到 stk.top().first > temperatures[i] 才把 temperatures[i] push 到 stk 中
class Solution {public: vector<int> dailyTemperatures(vector<int>& te ...
853. Car Fleet
題目網址: https://leetcode.cn/problems/car-fleet/
題意: 在一條單行道上, 有 n 輛車開往同一目的地, 目的地是幾英里外的 target。
給兩個整數 array position、speed, 其中 position[i] 是第 i 輛車的位置, speed[i] 是第 i 輛車的時速(英里/小時)。
一輛車永遠不會超過前面的另一輛車, 但它可以追上去, 並與前車以相同的速度緊接著行駛。此時, 我們可忽略這兩輛車之間的距離, 也就是說, 它們被假定處於相同的位置。
車隊是一些由行駛在相同位置、具有相同速度的車組成的非空集合。注意, 一輛車也可以是一個車隊。
即便一輛車在目的地才趕上了一個車隊, 它們仍然會被視作是同一個車隊。
返回到達目的地的車隊數量。
Solution：
想法：利用 Monotonic（遞減） Stack, 先使用 map 根據 position[i] 「由小到大」排序, 然後依序取出, 並計算 position[i] 到 target 所需的時間。如果當前所需的時間 time ≥ stk.top(), 則 ...
74. Search a 2D Matrix
題目網址: https://leetcode.cn/problems/search-a-2d-matrix/
題意: 設計一高效演算法來搜索 m x n matrix 中是否存在整數 target, matrix 滿足以下特性:
每列的元素由左到右按升序排列
每列的第一個元素 > 前一列的最後一個元素
Solution：
想法：利用 Binary Search, matrix 其實就是 1D 已排序的 array, 只是改成用 2D array 表達而已, 故將 matrix 看成 1D array, 然後還原回 2D array 座標來做 Binary Search
class Solution {public: bool searchMatrix(vector<vector<int>>& matrix, int target) { const int m = matrix.size(), n = matrix[0].size(); int left = 0, right = m ...
875. Koko Eating Bananas
題目網址: https://leetcode.cn/problems/koko-eating-bananas/
題意: Koko 喜歡吃香蕉。這里有 n 堆香蕉, 第 i 堆中有 piles[i] 根香蕉。警衛已經離開了, 並且將在 h 小時後回來。
Koko 可以決定她吃香蕉的速度 k （單位：根 / 小時）。每個小時, 她將會選擇其中一堆的香蕉, 並從中吃掉 k 根。如果這堆香蕉少於 k 根, 她將吃掉這堆所有的香蕉, 然後這一小時內都不會再吃更多的香蕉。
Koko 喜歡慢慢吃, 但仍然想在警衛回來前吃掉所有的香蕉。
返回她可以在 h 小時內吃掉所有香蕉的最小速度 k, 其中 k 為整數。
Solution：
想法：利用 Binary Search, 其中 k 的區間為 [1, max(piles)], 因為 Koko 吃掉該堆所有的香蕉後, 這一小時內都不會再吃更多的香蕉, 所以 k 取到 max(piles) 即可。此外, left 不能為 0, 否則 mid 有可能為 0, 這會導致計算 time += ceil(1.0 * pile / mid) 時發 ...