## Make Array Non-decreasing or Non-increasing

• Time:O(n\log n)
• Space:O(n)

## C++

``````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;
}
};
``````

## JAVA

``````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;
}
}
``````

## Python

``````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]))
``````