84. Largest Rectangle in Histogram
題目網址：https://leetcode.cn/problems/largest-rectangle-in-histogram/
題意：給 n 個非負整數, 用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰, 且寬度為 1。
返回柱狀圖中最大矩形的面積。
Solution 1：（TLE 無法通過）
想法：利用 Brute Force, 對於每一個 heights[i] 的寬度即為左、右邊第一個 < heights[i] 的位置, 其寬度為 right - left - 1 （left、right 都不包含在寬度中, 故要減一）
class Solution {public: int largestRectangleArea(vector<int>& heights) { int res = 0, n = heights.size(); for (int i = 0; i < n; ++i) { // 找到左邊第一個 < heights[i] 的位置 ...
4. Median of Two Sorted Arrays
題目網址：https://leetcode.cn/problems/median-of-two-sorted-arrays/
題意：給兩個排序過的 array nums1 和 nums2, 其大小分別為 m 和 n, 返回這兩個 array 排序過的中位數。
設計 $O(log(m+n))$ time 的演算法。
Solution 1：
想法：利用 Binary Search, 我們可以用分隔線將兩個 sorted array 分割成兩邊, 而中位數只與紅線兩側的元素有關。因為是 sorted array, 所以我們用 Binary Search 找出正確的分割線位置, 需滿足以下條件：
當 m + n 為偶數時, 紅線左邊的元素個素和右邊的元素個數相等。中位數為分割線左邊最大元素、分割線右邊最小元素之平均
當 m + n 為奇數時, 紅線左邊的元素個素比右邊的元素個數多 1(這樣方便我們計算中位數)
e.g. nums1 = [1], nums2 = [2, 3] ➔ 紅線左邊元素 = [1,2], 紅線右邊元素 = [3]
➔ 我們可直接取紅線左邊元素值最大的數為 ...
435. Non-overlapping Intervals
題目網址：https://leetcode.cn/problems/non-overlapping-intervals/
題意：給一區間集合 intervals, 其中 intervals[i] = [start_i, end_i], 返回需要移除的最小區間個數, 使得剩下的區間互不重疊。
Solution：
想法：首先, 先將 intervals 做排序, 然後紀錄前一天的 end, 當有兩天 start 相同時, end 會取較小的那一個, 這樣才能最大化避免重疊
以下圖為例, sorting 後的 intervals = [[1,2], [1,3], [2,3], [3,4], 最一開始 [1,2] 和 [1,3] 我們會選擇捨棄 [1,3], 因為 [1,2] 的 end 較小, 若保留 [1,3] 則會和後面的 [2,3] 重疊
class Solution {public: int eraseOverlapIntervals(vector<vector<int>>& intervals) { ...
253. Meeting Rooms II
題目網址：https://leetcode.cn/problems/meeting-rooms-ii/
題意：給一 array intervals, 其中 intervals[i] = [start_i, end_i], 返回所需的最小會議室數量。
注意：(0, 8) 和 (8, 10) 並不衝突
Solution 1：
想法：利用 heap 來紀錄所有會議室的 end, 並每次取 heap 中最小的, 來確認跟當前 interval 是否有衝突
若有, 則將當前 interval.end 加入到 heap 中
若沒有, 則把 top 取代為當前 interval.end（先 pop(), 再 push(newEnd)）
class Solution {public: int minMeetingRooms(vector<Interval> &intervals) { int res = 1; priority_queue<int, vector<int>, greater<& ...
48. Rotate Image
題目網址：https://leetcode.cn/problems/rotate-image/
題意：給一 n x n 的 2D array 表示一個 image, 請將 image 順時針旋轉 90 度。
注意：請使用 in-place 演算法
Solution 1：
想法：將 matrix 由外而內分成好幾層, 每一層依序交換以完成旋轉
class Solution {public: void rotate(vector<vector<int>>& matrix) { const int n = matrix.size(); // 想像從 (0, 0) 沿著對角線往中心點前進(n為奇數時中心不用旋轉, 故為 i < n / 2) for (int i = 0; i < n / 2; ++i) { // 每層共 n-2*(i+1) 個元素, 每往內一層元素個數就會減2, 減掉最左、最右兩個數 // i 為起始 ...