首页 > 其他 > 详细

HackerRank "AND xor OR"

时间:2015-11-23 16:26:44      阅读:295      评论:0      收藏:0      [点我收藏+]

Actually I think problem statement is somewhat misleading. No need to mention range [L, R] at all.

The intention is a variation to "Largest Rectangle" which is a classic stack problem on LeetCode.

But you need to run Largest Rectangle twice: increased and decreased.

技术分享
#include <cmath>
#include <stack>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int n; cin >> n;
    vector<int> in(n);
    for(int i = 0; i < n; i ++)
        cin >> in[i];
    
    int ret = 0;
    {
        in.push_back(0); 
        stack<int> stk;
        for (int i = 0; i < in.size(); i++)
        {
            if (stk.empty() || in[i] > stk.top())
            {
                stk.push(in[i]);
            }
            else
            {
                int lastV = stk.top(); stk.pop();
                if (!stk.empty())
                {
                    ret = std::max(ret, (lastV ^ stk.top()));            
                    //cout << lastV << "-" << stk.top() << "=" << (lastV ^ stk.top()) << endl;
                }
                i--;
            }
        }
        in.pop_back();
    }
    {
        
        stack<int> stk;
        in.insert(in.begin(), 0);
        for (int i = in.size() - 1; i >= 0; i --)
        {
            if (stk.empty() || in[i] > stk.top())
            {
                stk.push(in[i]);
            }
            else
            {
                int lastV = stk.top(); stk.pop();
                if (!stk.empty())
                {
                    ret = std::max(ret, (lastV ^ stk.top()));            
                    //cout << lastV << "-" << stk.top() << "=" << (lastV ^ stk.top()) << endl;
                }
                i++;
            }
        }
    }
    
    cout << ret << endl;
    return 0;
}
View Code

HackerRank "AND xor OR"

原文:http://www.cnblogs.com/tonix/p/4988677.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!