7. Stack problems

// Valid parentheses — O(n)
static bool IsValid(string s)
{
    var stack = new Stack<char>();
    var pairs = new Dictionary<char, char> { [')'] = '(', [']'] = '[', ['}'] = '{' };
    foreach (var c in s)
    {
        if (pairs.ContainsValue(c)) stack.Push(c);
        else if (pairs.TryGetValue(c, out var open))
        {
            if (stack.Count == 0 || stack.Pop() != open) return false;
        }
    }
    return stack.Count == 0;
}

// Next greater element — monotonic stack O(n)
static int[] NextGreater(int[] a)
{
    var result = Enumerable.Repeat(-1, a.Length).ToArray();
    var stack = new Stack<int>();                    // indexes waiting for a greater value
    for (int i = 0; i < a.Length; i++)
    {
        while (stack.Count > 0 && a[stack.Peek()] < a[i]) result[stack.Pop()] = a[i];
        stack.Push(i);
    }
    return result;
}