Как сравнить целые числа в 2 стеках в O (n)?

Question

У меня есть два стека s1 и s2.s1 содержит отрицательные целые числа и s2 содержит положительные целые числа.Оба стека уже отсортированы от минимального значения (внизу) к максимальному (вверху).x1 и x2 являются целыми числами в s1 и s2.Я хотел бы проверить оба стека, чтобы увидеть, является ли [x1 + x2 = данное целое число i].Каков наилучший способ (или способ) сделать это в O (n)?

Обновление: x1 и x2 являются целыми числами ... извините

обновление 2: метод возвращает логическое значение и будет иметь следующие параметры:

boolean method(Stack s1, Stack s2, int i)

метод вернет true, если любое целое число x1 в s1 + любое целое число x2 в s2 = i

Answer 1

Полагаю, вы имеете в виду, что любое число в s1 + любое число в s2 является заданным целым числом i.

Если это так,

1. Выскочите из верхней части обоих стеков
2. Добавьте их
3. Они равны i
   1. Да -> Вы закончили
4. Это больше, чем я?
   1. ДА -> тогда отрицательное число не может иметь аналога, выбросить его, выкинуть следующее отрицательное число из s1, перейти к 2
   2. НЕТ -> затем положительное числоможет не иметь аналога, выбросить его, вытолкнуть следующий положительный номер из s2, перейти к 2

(в любой момент, если стек пуст, вы сделали -- ответа нет)

РЕДАКТИРОВАТЬ: Я думаю, что я не прав на шаге 4 на основе вашего порядка сортировки - но эта основная идея должна быть близка.