Re: [閒聊] 每日leetcode

看板Marginalman作者Rushia (早瀬ユウカの体操服 )時間1年前 (2024/12/14 18:00)推噓1(1推 0噓 0→)

※ 引述《dont (dont)》之銘言： : 2762. Continuous Subarrays 今天這題好麻煩喔算滿足條件的子陣列數量會想到用滑動窗口陣列可能會是 [5,3,7] 或 [5,7,3] 這種CASE 不能只檢查窗口的頭部，要找到窗口裡的最大值和最小值比較然後一直POP到兩個條件都滿足如果不call treemap這種map+實作排序的資料結構真的會麻煩要死 Java code: ------------------------------------------------------ class Solution { public long continuousSubarrays(int[] nums) { int n = nums.length; long res = 0; int l = 0; TreeMap<Integer, Integer> map = new TreeMap<>(); for (int r = 0; r < n; r++) { int min = map.isEmpty() ? nums[r] : map.firstKey(); while (Math.abs(min - nums[r]) > 2) { decreaseCountMap(map, nums[l++]); min = map.isEmpty() ? nums[r] : map.firstKey(); } int max = map.isEmpty() ? nums[r] : map.lastKey(); while (Math.abs(max - nums[r]) > 2) { decreaseCountMap(map, nums[l++]); max = map.isEmpty() ? nums[r] : map.lastKey(); } map.put(nums[r], map.getOrDefault(nums[r], 0) + 1); res += (r - l + 1); } return res; } void decreaseCountMap(Map<Integer, Integer> map, int val) { if (map.get(val) == 1) { map.remove(val); } else { map.put(val, map.get(val) - 1); } } } ----------------------------------------------------------- -- https://i.imgur.com/R8vs1tZ.jpeg