Here is the link.
C# | Quick learner | Maximum heap | Sorted<Tuple<int, int>> | Tip: Add twice
June 3, 2022
I like to be a quick learner. I could not figure out the trick by reading C++, Java code shared by votrubac. So I debugged and then figured out how to make the test case work.
Test case | {3, 2, 4, 5, 0} | Trick: Add twice into the max heap
I like to go over the test case {3, 2, 4, 5, 0} and explain why it takes 4 operations to make a non-decreasing order in reverse order.
I chose to use C# SortedSet<Tuple<int, int>> to simulate a maximum heap.
I tried to work on the above case step by step by myself. I am working on
cost(nums, -1)
First, last element in the array, index = 4, add it to Max heap, heap - new Tuple<int, int>, (0, 0)
Next, index = 3, value 5, add it to heap, (5, 1)
Next, index = 2, value 4, heap.Max.Item1 = 5 > 4, so result variable increments (5 - 4) = 1, remove (5, 1) from heap,
add (4, 2) to heap <- inside if statement
if (heap.Count > 0 && heap.Max.Item1 > current)
{
result += heap.Max.Item1 - current;
heap.Remove(heap.Max);
heap.Add(new Tuple<int, int>(current, count++));
}
Next, it is to add (4, 3) to the heap by executing the statement outside if statement
// explain: why {3, 2, 4, 5, 0} reverse order, 4 will be added twice?
heap.Add(new Tuple<int, int>(current, count++));
Mext. it is to add (2, 4) to the heap, and result += (4 - 2), result = 3, remove (4, 3) from heap
Last, it is to add (3, 5) to the heap, and result += (4 - 3), result = 4, remove (4, 2) from heap.
votrubac | Analysis
I just quickly copied the idea and analysis from votrubac in the following:
The greedy logic is quite tricky. We process numbers left-to-right, and put them into a max heap.
When the current number n is smaller than the largest so far m, we know that we need to do m - n adjustments.
Now, the tricky part. We can increase n and/or decrease m so that they become the same. But for the purpose of the greedy algorithm, we assume we decrease m all the way to be the same as n, and put the new value to the heap.
The following C# code passes online judge.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _2263_make_array_non_decreasing
{
class Program
{
static void Main(string[] args)
{
var result = ConvertArray(new int[]{3, 2, 4, 5, 0});
Debug.Assert(result == 4);
}
/// <summary>
/// study code
/// https://leetcode.com/problems/make-array-non-decreasing-or-non-increasing/discuss/2011905/Greedy
/// </summary>
/// <param name="nums"></param>
/// <returns></returns>
public static int ConvertArray(int[] nums)
{
return Math.Min(cost(nums), cost(nums, -1));
}
/// <summary>
/// checklist:
/// 1. Maximum heap
/// 2. Tricky part - greedy - decrease m all the way to be the same as n, and put the new value to the heap
/// </summary>
/// <param name="nums"></param>
/// <param name="d"></param>
/// <returns></returns>
private static int cost(int[] nums, int d = 1)
{
int result = 0;
var heap = new SortedSet<Tuple<int, int>>();
var length = nums.Length;
var count = 0;
for (int i = (d == 1 ? 0 : length - 1); i < length && i >= 0; i += d)
{
var current = nums[i];
if (heap.Count > 0 && heap.Max.Item1 > current)
{
result += heap.Max.Item1 - current;
heap.Remove(heap.Max);
heap.Add(new Tuple<int, int>(current, count++));
}
// explain: why {3, 2, 4, 5, 0} reverse order, 4 will be added twice?
heap.Add(new Tuple<int, int>(current, count++));
}
return result;
}
}
}