Skip to content

2263. Make Array Non-decreasing or Non-increasing πŸ‘ΒΆ

  • Time: O(nlog⁑n)O(n\log n)
  • Space: O(n)O(n)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  int convertArray(vector<int>& nums) {
    return min(cost(nums), cost(negative(nums)));
  }

 private:
  int cost(const vector<int>& nums) {
    int ans = 0;
    priority_queue<int> maxHeap;

    // Greedily make `nums` non-decreasing.
    for (const int num : nums) {
      if (!maxHeap.empty() && maxHeap.top() > num) {
        ans += maxHeap.top() - num, maxHeap.pop();
        maxHeap.push(num);
      }
      maxHeap.push(num);
    }

    return ans;
  }

  vector<int> negative(const vector<int>& nums) {
    vector<int> A(nums);
    for (int& a : A)
      a *= -1;
    return A;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public int convertArray(int[] nums) {
    return Math.min(cost(nums), cost(negative(nums)));
  }

  private int cost(int[] nums) {
    int ans = 0;
    Queue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

    // Greedily make `nums` non-decreasing.
    for (final int num : nums) {
      if (!maxHeap.isEmpty() && maxHeap.peek() > num) {
        ans += maxHeap.poll() - num;
        maxHeap.offer(num);
      }
      maxHeap.offer(num);
    }

    return ans;
  }

  private int[] negative(int[] nums) {
    int[] A = nums.clone();
    for (int i = 0; i < A.length; ++i)
      A[i] *= -1;
    return A;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def convertArray(self, nums: list[int]) -> int:
    def cost(nums: list[int]) -> int:
      ans = 0
      minHeap = []

      # Greedily make `nums` non-increasing.
      for num in nums:
        if minHeap and minHeap[0] < num:
          ans += num - heapq.heappushpop(minHeap, num)
        heapq.heappush(minHeap, num)

      return ans

    return min(cost(nums), cost([-num for num in nums]))
Buy Me A Coffee
Thanks for stopping by! If you find this site helpful, consider buying me some protein powder to keep me fueled! πŸ˜„