C# cases TLE time is too short?


  • 0
    B

    The following O(n) code from geekforgeek got TLE. But after replace st.Count() with a variable manually record stack count, the code is accepted. So is it because Stack.Count() slow or just because leetcode cases have too short time limit?

    btw: According to MS document, Stack.Count() is O(1) time complexity.

    public int LargestRectangleArea(int[] heights)
        {
            int len = heights.Length;
            if (len == 0)
                return 0;
    
            Stack<int> st = new Stack<int>();
            int max = 0;
            
            for(int i=0; i<len; i++)
            {
                while(st.Count() > 0)
                {
                    var top = st.Peek();
                    if (heights[i] < heights[top])
                    {
                        st.Pop();
                        var left = (st.Count() == 0) ? -1 : st.Peek();
                        max = Math.Max(max, (heights[top] * (i - 1 - left)));
                    }
                    else
                        break;
                }
                st.Push(i);
            }
            while(st.Count() > 0)
            {
                var top = st.Pop();
                var left = (st.Count() == 0) ? - 1 : st.Peek();                
                max = Math.Max(max, (heights[top] * (len - 1 - left)));
            }
    
            return max;
        }
    

    Code with manual record variable stlen:

    public int LargestRectangleArea2(int[] heights)
        {
            int len = heights.Length;
            if (len == 0)
                return 0;
    
            Stack<int> st = new Stack<int>();
            int max = 0;
            int stlen = 0;
    
            for (int i = 0; i < len; i++)
            {
                while (stlen > 0)
                {
                    var top = st.Peek();
                    if (heights[i] < heights[top])
                    {
                        st.Pop();
                        stlen--;
                        var left = (stlen == 0) ? -1 : st.Peek();
                        max = Math.Max(max, (heights[top] * (i - 1 - left)));
                    }
                    else
                        break;
                }
                st.Push(i);
                stlen++;
            }
            while (stlen > 0)
            {
                var top = st.Pop();
                stlen--;
                var left = (stlen == 0) ? -1 : st.Peek();
                max = Math.Max(max, (heights[top] * (len - 1 - left)));
            }
    
            return max;
        }

Log in to reply
 

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