前往
大廳
主題

LeetCode - 2091. Removing Minimum and Maximum From Array 解題心得

Not In My Back Yard | 2022-05-28 12:00:15 | 巴幣 0 | 人氣 202

題目連結:


題目意譯:
你被給定一索引值從 0 開始的相異整數陣列 nums。

現在 nums 中有一元素有著最低值以及一元素有著最高值。我們依序叫這些數值為最小以及最大值。你的目標是從陣列移除掉這兩個元素。

一次的刪除只會是從陣列的前端或是尾端移除掉一個元素。

回傳移除掉最小以及最大值這兩個元素最少所需的刪除次數。

限制:
1 ≦ nums.length ≦ 10 ^ 5
-10 ^ 5 ≦ nums[i] ≦ 10 ^ 5
nums 中的整數皆相異。



範例測資:
範例 1:
輸入: nums = [2,10,7,5,4,1,8,6]
輸出: 5
解釋:
陣列中最小的元素為 nums[5],其為 1。
陣列中最大的元素為 nums[1],其為 10。
我們可以藉由移除前面兩個元素以及後面三個元素來移除掉最小和最大值。
總計是 2 + 3 = 5 次刪除,其為最少的可能次數。

範例 2:
輸入: nums = [0,-4,19,1,8,-2,-3,5]
輸出: 3
解釋:
陣列中最小的元素為 nums[1],其為 -4。
陣列中最大的元素為 nums[2],其為 19。
我們可以藉由移除前面三個元素來移除掉最小和最大值。
總計是 3 次刪除,其為最少的可能次數。

範例 3:
輸入: nums = [101]
輸出: 1
解釋:
陣列中只有一個元素,因此其暨為最小以及最大值。
我們可以藉由一次刪除將其移除。


解題思維:
首先,掃過陣列去找到最小和最大值(如果整個陣列只有一個數字,則直接回傳 1 即可,如同範例 3)。假設兩個極值發生的位置分別為索引值 X 和 Y,其中 X < Y。

此時可以看到,我們實際上只有三種可能為最佳的刪除法:
一:從前面刪到 X 為止(含),然後從後面刪到 Y 為止(含)。也就是陣列剩索引值 X + 1 ~ Y - 1 的元素;
二:從前面刪到 Y 為止(含)。也就是陣列剩索引值 Y + 1 之後的元素;
三:從後面刪到 X 為止(含)。也就是陣列剩索引值 X - 1 之前的元素。

而上面之中刪除次數最少的即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作