字节跳动2018算法岗笔试题

利用预排序的方法，可以通过80%

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    int num = 0;
    cin >> num;
    if (num == 0) return 0;
    vector<vector<int>> points(num, vector<int> (2, -1));
    for (int i = 0; i < num; i++) {
        cin >> points[i][0];
        cin >> points[i][1];
    }
    auto cmp = [&] (const vector<int>& a, const vector<int>& b) {
        return a[1] > b[1];
    };
    sort(points.begin(), points.end(), cmp);
    cout<<points[0][0]<<" "<<points[0][1]<<" "<<endl;
    int curX = points[0][0];
    for (int i = 1; i < points.size(); i++) {
        if (points[i][0] > curX) {
            cout<<points[i][0]<<" "<<points[i][1]<<" "<<endl;
            curX = points[i][0];
        }
    }
    return 0;
}

因为每次处理的都是一个包含最小值的区间，因此可以利用单调栈，对包含每一个最小值的最长区间做线性处理。十分巧妙。

#include<vector>
#include<stack>
#include<iostream>
using namespace std;
int main() {
    int n = 0;
    cin >> n;
    stack<int> st;
    vector<int> vec(n);
    vector<int> preSum(n + 1, 0);
    int maxVal = -1;
    for (int i = 0; i < n; i++) {
        cin >> vec[i];
        preSum[i + 1] = preSum[i] + vec[i];
    }
    for (int i = 0; i < n; i++) {
        while (!st.empty() && vec[i] < vec[st.top()]) {
            auto cur = st.top();
            st.pop();
            if (!st.empty()) {
                maxVal = max(maxVal, (preSum[i] - preSum[st.top() + 1])*vec[cur]);
            }
            else maxVal = max(maxVal, preSum[i]*vec[cur]);
        }
        st.push(i);
    }
    while (!st.empty()) {
        auto cur = st.top();
        st.pop();
        if (!st.empty()) {
            maxVal = max(maxVal, (preSum[n]-preSum[st.top() + 1])*vec[cur]);
        }
        else maxVal = max(maxVal, preSum[n]*vec[cur]);
    }
    cout<<maxVal;
    return 0;
}