C# Solution


  • 0
    J

    The idea is to find the first occurrence where the previous digit is greater than the current digit. Reduce the previous digit by 1 and check if the condition still holds good. If not reduce its previous digit by 1 and check. Once the condition is true set all the digits from that index as 9.
    For e.g. 1331 :
    Condition fails for 3rd and 4th digit. Reduce the 3rd digit by 1, hence 1321.
    But now the condition fails between 3rd and 2nd digit. Reduce the second digit by 1, hence it is 1221. Set all the digits from 3rd digit until the end as 9. Hence 1299.

    public int MonotoneIncreasingDigits(int N)
            {
                var list = new List<int>();
                while (N > 0)
                {
                    list.Add(N % 10);
                    N = N / 10;
                }
                if(list.Count == 0) return 0;                
                var array = list.ToArray();
                Array.Reverse(array);
                var stack = new Stack<int>();
                stack.Push(array[0]);           
                int i = 1;            
                while (i < array.Length)
                {
                    if (array[i] >= stack.Peek())
                        stack.Push(array[i]);
                    else
                    {
                        while (stack.Count > 0)
                        {
                            int prev = stack.Pop();
                            prev--;
                            i--;
    
                            if (stack.Count == 0 || (stack.Count > 0 && prev >= stack.Peek()))
                            {
                                stack.Push(prev);
                                i++;
                                break;
                            }
                        }
    
                        while (i < array.Length)
                        {
                            stack.Push(9);
                            i++;
                        }
                        break;
                    }                
                    i++;
                }
                return CreateNumFromStack(stack);
            }
    
            private int CreateNumFromStack(Stack<int> array)
            {
                var r = array.Reverse().ToArray();
                var str = string.Empty;
                int i = 0;
                while (i < r.Count())
                {
                    str += r[i];
                    i++;
                }
                return int.Parse(str);
            }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.