Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

Arithmetic expression tree and Evaluate Reverse Polish Notation

There's a problem called
Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

The problem becomes simple if we know the rule of using a stack to evaluate the reverse polish notation (RPN).
1. Push every numbers in to the stack
2. When an operand occurs, pop the first 2 numbers out of the stack and calculate c=(a operand b)
3. Push c into the stack


    int evalRPN(vector<string> &tokens) {
       
        int n = tokens.size();
       
        stack<int> numbers;
        string op ="+-*/";
       
        for (int i=0; i<n; i++)
        {
            int j=0;
            int t = op.find(tokens[i]);
           
            if (t!=-1)
            {
                int a = numbers.top();
                numbers.pop();
                int b = numbers.top();
                numbers.pop();
               
                switch(t){
                case 0 :
                j = a+b;
                break;
                case 1:
                j = b-a;
                break;
                case 2:
                j = a*b;
                break;
                case 3:
                j = b/a;
                break;
                }
                numbers.push(j);
            }
            else
            {
                j = atoi(tokens[i].c_str());
                numbers.push(j);
            }
           
        }
       
        return numbers.top();
    }

Even shorter version without many APIs

class Solution {
public:
    int evalRPN(vector<string> &tokens) {
       stack<int> numStack;
       for(int tokI = 0; tokI < tokens.size(); ++ tokI)
           if(tokens[tokI] == "*" || tokens[tokI] == "+" || tokens[tokI] ==
"/" || tokens[tokI] == "-")
           {
              int val1 = numStack.top(); numStack.pop();
              int val2 = numStack.top(), res; numStack.pop();
              if(tokens[tokI] == "+")
                  res = val1 + val2;
              else if(tokens[tokI] == "*")
                  res = val1 * val2;
              else if(tokens[tokI] == "-")
                  res = val2 - val1;
              else
                  res = val2 / val1;
              numStack.push(res);
           }
           else
              numStack.push(atoi(tokens[tokI].c_str()));
       return numStack.top();
    }
};


Related problems can also be solved with info from these sources

http://fredosaurus.com/notes-cpp/ds-trees/10exptrees.html

http://penguin.ewu.edu/cscd300/Topic/ExpressionTree/index.html

http://nova.umuc.edu/~duchon/exTrees/

Longest Valid Parentheses

Problem:

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Idea：
1. Need to push the indices of '('
2. last needs to be initialized as -1 instead of 0 for    lmax = max(lmax,i-last); work

    int longestValidParentheses(string s) {
        vector<int> left;
       int n=s.size();
       int last=-1,lmax=0;
       for (int i=0; i<n; i++)
       {
            if (s[i]=='(')
             {
              left.push_back(i);
              }
              else if (s[i]==')')
              { 
                     if (left.empty())
                     {
                         last=i;
                    }
                    else
                    {
                        left.pop_back();
                        if (left.empty())
                        {
                            lmax = max(lmax,i-last);
                        }
                        else
                        lmax = max(lmax,i-left.back());
                    }
              }
       }
       return lmax;
    }

Welcome!

I'm a scientist/software development engineer and like to post some technical stuff here. Hope you enjoy the content.